Cod sursa(job #1242290)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 14 octombrie 2014 11:22:20
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
int n, m, i, j, aux, o, k, q, w;
long long r;
char a[1000005], v[1000005], pp[1000005];
int main()
{
    freopen("mins.in", "r", stdin);
    freopen("mins.out", "w", stdout);

    scanf("%d%d", &n, &m);
    n--;m--;
    if(n>m)
    {
        m+=n;
        n=m-n;
        m=m-n;
    }
    r=1LL*n*m;
    for(i=2;i<=n;i++)
    {
        if(!v[i])
        {
            for(j=i+i;j<=n;j+=i)
                v[j]=1, a[j]++;
            a[i]=1;
            if(1LL*i*i<=n)
                for(j=i*i;j<=n;j+=i*i)
                    pp[j]=1;
        }
    }

    for(i=2;i<=n;i++)
    {
        if(pp[i]) continue;
        if(a[i]&1)
            r-=(n/i)*(m/i);
        else
            r+=(n/i)*(m/i);
    }
    printf("%lld", r);
    return 0;
}