Pagini recente » Cod sursa (job #3284318) | Cod sursa (job #725471) | Cod sursa (job #1161863) | Cod sursa (job #1012460) | Cod sursa (job #2494001)
#include <fstream>
using i64=long long;
using namespace std;
ifstream in("mins.in");
ofstream out("mins.out");
const int NMAX=1000000;
int mo[NMAX+5];
bool ciur[NMAX+5];
int ans[NMAX+5];
void Ciur(int n)
{
ciur[1]=ciur[0]=1;
for(int i=4;i<=n;i+=2)
ciur[i]=1;
for(int i=3;i*i<=n;i+=2)
if(ciur[i]==0)
for(int j=i*i;j<=n;j+=i*2)
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=i;j<=n;j+=i)
ans[j]+=mo[i]*(m/i);
for(int i=1;i<=n;i++)
rez=(long long)(rez+ans[i]);
out<<1LL*n*m-rez<<'\n';
return 0;
}