Cod sursa(job #1695334)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 26 aprilie 2016 22:18:03
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NM=1e6+5;

bool Put2[NM];
int n,m,i,j, d[NM];
long long ans,x;

int main()
{
    freopen("mins.in", "r", stdin);
    freopen("mins.out", "w", stdout);

    scanf("%d%d", &n, &m);
    --n; --m;
    if(n>m) swap(n,m);

    for(i=2; i<=n; ++i)
    if(!d[i])
    {
         for(j=i; j<=n; j+=i)
         {
             ++d[j];
             if(1LL*i*i<=1LL*n && j%(i*i)==0) Put2[j]=1;
         }
    }

    ans=1LL*n*m;

    for(i=2; i<=n; ++i)
    if(!Put2[i])
    {
         x=1LL*(n/i)*(m/i);
         if(d[i]&1) ans-=x;
         else ans+=x;
    }

    printf("%lld\n", ans);

    return 0;
}