Cod sursa(job #1410897)

Utilizator AndreosAndrei Otetea Andreos Data 31 martie 2015 12:35:24
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX=1000001;
int ciur[NMAX];
bool put[NMAX];
int main()
{
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);
    int c,d,lmax,i,j;
    long long sol;
    scanf("%d%d",&c,&d);
    c--;
    d--;
    lmax=min(c,d);
    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("%lld",sol);
    return 0;
}