Cod sursa(job #2007591)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 3 august 2017 13:37:02
Problema Mins Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>

using namespace std;
int c[1000005];
long long i,j,nr,x,y;
bool v[1000005],p[1000005];
int cmmdc(int a, int b)
{
    int r=0;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    ifstream f("mins.in");
    ofstream g("mins.out");
    f>>x>>y;
    /*for(i=1; i<x; i++)
    for(j=1; j<y; j++)
    {
        if(cmmdc(i,j)==1) nr++;
    }
    g<<nr<<'\n';*/
    nr=0;
    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[j]=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;
}