Cod sursa(job #2201730)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 5 mai 2018 18:05:40
Problema Mins Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#include <algorithm>
#define NMAX 1000005

using namespace std;

int cnt[NMAX];
int c,d;
long long sol = 0;

inline long long formula(int i)
{
    return 1LL*(c/i)*(d/i);
}

int main()
{
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);
    int x,y;
    scanf("%d%d",&x,&y);
    c = min(x,y);
    d = max(x,y);
    c--;
    d--;
    sol = 1LL * c * d;
    for(int i = 2 ; i <= c ; i++)
    {
        if(!cnt[i])
        {
            sol -= 1LL * formula(i);
            for(int j = i ; j <= d ; j += i)
                ++cnt[j];
        }
        else
        {
            if(cnt[i]>=2)
            {
                sol += 1LL * formula(i) * (cnt[i]-1);
                for(int j = i ; j <= d ;j += i)
                    --cnt[j];
            }
        }
    }
    printf("%lld",sol);
    return 0;
}