Cod sursa(job #1019599)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 31 octombrie 2013 16:52:57
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<fstream>

using namespace std;

const int maxn=1000005;

long a[maxn],c,d,i,j,mint;
long long sol;

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

    scanf("%ld%ld",&c,&d);
    --c,--d;
    mint=min(c,d);
    sol=1LL*c*d;
    for(i=2;i<=mint;++i)
    {
        if(a[i]==0)
        {
            if(i<=10000)
                for(j=i*i;j<=mint;j+=i*i)
                    a[j]=-1;
            for(j=i;j<=mint;j+=i)
                if(a[j]!=-1)
                    ++a[j];
        }
        if(a[i]!=-1)
            if(a[i]&1)
                sol-=1LL*(c/i)*(d/i);
            else
                sol+=1LL*(c/i)*(d/i);
    }
    printf("%lld\n",sol);
    return 0;
}