Cod sursa(job #2493990)

Utilizator rares_ciocieaRares Andrei Ciociea rares_ciociea Data 17 noiembrie 2019 11:06:21
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
using i64=long long;
using namespace std;
ifstream in("mins.in");
ofstream out("mins.out");
const int NMAX=1000000;
char mo[NMAX+5];
bool ciur[NMAX+5];
int ans[NMAX+5];
void Ciur(int n)
{
    ciur[1]=ciur[0]=1;
    for(int i=2;i*i<=n;i++)
        if(ciur[i]==0)
            for(int j=i*i;j<=n;j+=i)
                ciur[j]=1;
}
void miu(int n)
{
    for(int i=1;i<=1000000;i++)
        mo[i]=-1;
    for(int i=2;i*i<=n;i++)
        for(int j=i*i;j<=n;j+=i*i)
            mo[j]=0;
    for(int i=2;i<=n;i++)
        if(ciur[i]==0)
        for(int j=i;j<=n;j+=i)
            mo[j]=(-1)*mo[j];

}

int main()
{

    int n,m;
    long long rez(0);
    in>>n>>m;
    n--;m--;
    Ciur(n);
    miu(n);
    //for(int i=2;i<=n;i++)
     //   for(int j=2;j<=n;j+=i)
     //   ans[j]+=mo[i]*(m/i);
    //for(int i=1;i<=n;i++)
    //    rez=(long long)(rez+ans[i]);
    for(int i=2;i<=n;i++)
       rez=rez+1LL*(n/i)*(m/i)*mo[i];
    out<<1LL*n*m-rez<<'\n';
    return 0;
}