Cod sursa(job #700197)

Utilizator VmanDuta Vlad Vman Data 1 martie 2012 03:05:06
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 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;   
}