Cod sursa(job #983104)

Utilizator stefan.friptuPetru Stefan Friptu stefan.friptu Data 10 august 2013 20:29:38
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;
}