Cod sursa(job #2007582)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 3 august 2017 13:17:54
Problema Mins Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>

using namespace std;
int c[1000005];
long long i,j,nr,x,y;
bool v[1000005],p[1000005];
int main()
{
    ifstream f("mins.in");
    ofstream g("mins.out");
    f>>x>>y;
    x--;
    y--;
    if(x<y) swap(x,y);
    for(i=1; i<=y; i++)
    {
        c[i]=1;
        p[i]=1;
    }
    for(i=2; i<=y; i+=2)
    {
        c[i]*=-1;
        v[i]=1;
        if(i%4==0) p[i]=0;
    }
    i=3;
    while(i<=y)
    {
        for(j=i; j<=y; j+=i)
        {
            c[j]*=-1;
            v[i]=1;
            if(j%(i*i)==0) p[j]=0;
        }
        while(i<=y&&v[i]) i+=2;
    }
    for(i=1; i<=y; i++)
    {
        if(p[i]) nr+=1LL*c[i]*(x/i)*(y/i);
    }
    g<<nr<<'\n';
    f.close(); g.close();
    return 0;
}