Cod sursa(job #912589)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 12 martie 2013 16:09:19
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <cstdio>
  
#define Nmax 1000001
  
inline int min(int a, int b) { return a<b?a:b; }
  
int N, M, D[Nmax], i, j, top;
long long tot;
  
int main()
{
     freopen("mins.in","r",stdin);
     freopen("mins.out","w",stdout);
       
     scanf("%d %d", &N, &M);
     top = min(N, M) - 1;
       
     for (i=2; i<=top; ++i)
     {
         if (!D[i])
         {
          for (j=i; j<=top; j+=i) ++D[j];
          if (i <= top / i) for (j=i*i; j<=top; j+=i*i) D[j] = -10000000;         
         }
         if (D[i]>=0) 
            if (D[i] & 1) tot -= (long long)((N-1)/i) * ((M-1)/i);
               else tot += (long long)((N-1)/i) * ((M-1)/i);
     }
       
     printf("%lld\n", tot + (long long)(N-1) * (M-1));
       
     return 0;   
}