Cod sursa(job #341744)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 19 august 2009 14:03:35
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
 #include<stdio.h>  
 #define N 1000100  
 long long n,m,i,j,p[N],pp[N],s[N],sol;  
 void read(),solve();  
 int main()  
 {  
     read();  
     solve();  
     return 0;  
 }  
 void read()  
 {  
     freopen("mins.in","r",stdin);  
     freopen("mins.out","w",stdout);  
     scanf("%lld%lld",&n,&m);  
     if(n<m)n^=m^=n^=m;  
 }  
 void solve()  
 {  
     p[1]=1;s[1]=1;  
     for(i=2;i<m;i++)  
     {  
         if(p[i])continue;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])continue;  
         s[i]=-s[i/p[i]];  
         sol+=s[i]*(m/i)*(n/i);  
     }  
     printf("%lld\n",sol);  
 }