Cod sursa(job #894428)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 26 februarie 2013 21:14:42
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;   
}