Cod sursa(job #1409552)

Utilizator Dragne.Andrei11Dragne Andrei Dragne.Andrei11 Data 30 martie 2015 16:22:44
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <algorithm>
#define nmax 1000000

using namespace std;

int ciur[nmax+1];
bool put[nmax+1];
int c, d;
int main()
{
    freopen("mins.in", "r", stdin);
    freopen("mins.out", "w", stdout);
    scanf("%d%d", &c, &d);
    c--;
    d--;
    int lmax=min(c, d);
    int i, j;
    long long sol=1LL*c*d;
    for(i=2;i<=lmax;++i)
    {
        if(!ciur[i])
        {
            for(j=i;j<=lmax;j+=i)
                ciur[j]++;
            if(1LL*i*i<=lmax)
                for(j=i*i;j<=lmax;j+=i*i)
                    put[j]=true;
        }
    }
    for(i=2;i<=lmax;++i)
    {
        if(put[i]==false)
        {
            if(ciur[i]%2)
                sol-=1LL*(c/i)*(d/i);
            else
                sol+=1LL*(c/i)*(d/i);
        }
    }
    printf("%I64d", sol);

    return 0;
}