Pagini recente » Cod sursa (job #1252413) | Cod sursa (job #1465026) | Cod sursa (job #2864863) | Cod sursa (job #2985465) | Cod sursa (job #2837605)
#include <bits/stdc++.h>
using namespace std;
ifstream in("mins.in");
ofstream out("mins.out");
typedef long long ll;
const int lim=1e6+4;
vector<int> used;
int prod[lim];
int last[lim];
bool ok[lim];
int phi[lim];
int nrb[150];
int pr[150];
int lp[lim];
int b[150];
int c,d;
ll ans;
int main()
{
in>>c>>d; --c,--d;
if(c>d) swap(c,d);
for(int i=1;i<=c;++i)
prod[i]=1;
phi[1]=d;
ans+=1LL*d;
for(int i=1;i<=140;++i)
{
nrb[i]=__builtin_popcount(i)+1;
for(int j=0;;++j)
if(i&(1<<j))
{
b[i]=j;
break;
}
}
for(int i=2;i<=c;++i)
{
if(!ok[i])
{
for(int j=i;j<=c;j+=i)
ok[j]=true,
prod[j]*=i,
last[j]=i;
}
if(prod[i]!=i)
{
ans+=1LL*phi[prod[i]];
continue;
}
int aux=i;
while(aux>1)
{
used.push_back(last[aux]);
aux/=last[aux];
}
int nr=used.size()-1;
phi[i]=phi[i/used[0]];
phi[i]-=(d/used[0]);
pr[0]=used[0];
for(int a=1;a<(1<<nr);++a)
{
pr[a]=pr[(a^(1<<b[a]))]*used[b[a]+1];
if(nrb[a]%2==1)
phi[i]-=(d/pr[a]);
else phi[i]+=(d/pr[a]);
}
ans+=1LL*phi[i];
used.clear();
}
out<<ans<<'\n';
return 0;
}