Cod sursa(job #1752204)

Utilizator silkMarin Dragos silk Data 3 septembrie 2016 00:13:25
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <cstdio>
#define NMax 1000000
#define ll long long
#define MAX(a,b)((a)>(b)?(a):(b))
#define MIN(a,b)((a)<(b)?(a):(b))

int nrdiv[NMax+1];

int main(){
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);

    int i,j,n,m;
    ll ans;

    scanf("%d %d",&n,&m);
    --n; --m;

    ans = 0;
    for(i = 2; i <= MAX(n,m); ++i)
    if( nrdiv[i] >= 0 )
    {
        if( !nrdiv[i] )
            for(j = i; j <= NMax; j+=i) ++nrdiv[j];

        if( nrdiv[i]%2 || !nrdiv[i] ) ans = ans + 1LL*(m/i)*(n/i);
        else ans = ans - 1LL*(m/i)*(n/i);

        if( i <= 1000 )
            for(j = i*i; j <= NMax; j+=i*i) nrdiv[j] = -NMax;
    }

    printf("%lld\n", 1LL*n*m - ans );



return 0;
}