Cod sursa(job #1341010)

Utilizator usermeBogdan Cretu userme Data 12 februarie 2015 11:53:36
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>

FILE*f=fopen("mins.in","r");
FILE*h=fopen("mins.out","w");

int cnt[1100000],block[1100000];

int main (){
    int c,d,mi;
    long long sol;
    fscanf(f,"%d%d",&c,&d);
    --c;
    --d;
    sol=1LL*c*d;
    if ( c<d )
        mi=c;
    else
        mi=d;
    for ( int i=2;i<=mi;++i )
        if ( cnt[i]==0 ){
            for ( int j=i;j<=mi;j+=i)
                cnt[j]++;
            if ( 1LL*i*i>mi )
                continue;
            for ( int j=i*i;j<=mi;j+=i*i )
                block[j]=1;
        }
    for ( int i=2;i<=mi;++i )
        if ( !block[i] )
            if ( cnt[i]&1==1 )
                sol-=1LL*(c/i)*(d/i);
            else
                sol+=1LL*(c/i)*(d/i);
    fprintf(h,"%lld",sol);
    return 0;
}