Cod sursa(job #1458915)

Utilizator radudurlesteanuDurlesteanu Radu Stefan radudurlesteanu Data 8 iulie 2015 19:31:37
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include<cstdio>
#define N 1000100
long long n,m,i,j,p[N],pp[N],s[N],sol,aux;
int main()
{
freopen("mins.in","r",stdin);
freopen("mins.out","w",stdout);
scanf("%lld%lld",&n,&m);
if (n<m) {
          aux=n;
          n=m;
          m=aux;
         }
p[1]=1;s[1]=1;
for (i=2;i<m;i++)
    {
     if (p[i]);
     p[i]=i;
     for (j=i*i;j<m;j+=i) p[j]=i;
     for (j=i*i;j<m;j+=i*i) pp[j]=i;
    }
m--;n--;sol+=m*n;
for(i=2;i<=m;i++)
    {
     if (pp[i]) ;
     s[i]=-s[i/p[i]];
     sol+=s[i]*(m/i)*(n/i);
    }
printf("%lld\n",sol);
}