Pagini recente » Cod sursa (job #1609654) | Cod sursa (job #1684875) | Cod sursa (job #390749) | Cod sursa (job #2318938) | Cod sursa (job #3151825)
#include <bits/stdc++.h>
#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
ifstream fin ("mins.in");
ofstream fout ("mins.out");
const int NMAX=1e6+5;
long long mobius[NMAX];
bool ciur[NMAX];
long long prime[NMAX];
int kon;
void precompute_mobius()
{
int i,j;
for(i=1;i<=NMAX-5;i++)
mobius[i]=1;
for(i=2;i*i<=NMAX-5;i++)
{
if(!ciur[i])
{
for(j=i*i;j<=NMAX-5;j+=i)
ciur[j]=true;
}
}
for(i=2;i<=NMAX-5;i++)
{
if(!ciur[i])
prime[++kon]=i;
}
for(i=1;i<=kon;i++)
{
for(j=prime[i];j<=NMAX-5;j+=prime[i])
mobius[j]=-mobius[j];
}
for(i=1;i<=kon;i++)
{
if(1LL*prime[i]*prime[i]>NMAX-5)
break;
for(j=prime[i]*prime[i];j<=NMAX-5;j+=prime[i]*prime[i])
mobius[j]=0;
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
int n,m,i,saiz;
long long total=0;
precompute_mobius();
fin>>n>>m;
saiz=min(n,m);
for(i=1;i<saiz;i++)
total+=1LL*((n-1)/i)*((m-1)/i)*mobius[i];
fout<<total;
fin.close();
fout.close();
return 0;
}