Pagini recente » Cod sursa (job #517439) | Cod sursa (job #2398929) | Cod sursa (job #1878258) | Cod sursa (job #1942746) | Cod sursa (job #935853)
Cod sursa(job #935853)
#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[1000005][8];
int p[10];
long long pinex(int x,int y)
{
///numarul de numere <=x si prime cu y:
int ans=x,q,nr,f=dp[y][0];
for(int i=1;i<=f;i++)
p[i-1]=dp[y][i];
//generam submultimi cu factorii primi:
for(int i=1;i<(1<<f);i++)
{
nr=0;q=1;
for(int j=0;j<f;j++)
if(i&(1<<j))
nr++,q*=p[j];
if(nr&1) ans-=x/q;
else ans+=x/q;
}
return ans;
}
int main()
{
freopen("mins.in","r",stdin);
freopen("mins.out","w",stdout);
int n,m;long long ans=0;
scanf("%d%d",&m,&n);m--;n--;
if(m>n) swap(n,m);
//mai intai vedem patratul care se poate rezolva ∑phi(i)
for(int i=1;i<=m;i+=2) dp[i][0]=i;
for(int i=2;i<=m;i+=2) dp[i][0]=i/2;
for(int i=3;i<=m;i+=2)
if(dp[i][0]==i)
for(int j=i;j<=m;j+=i)
dp[j][0]=dp[j][0]/i*(i-1);
for(int i=1;i<=m;i++)
ans=ans+dp[i][0],dp[i][0]=0;
ans=2*ans-1;
//pregenerari pentru descompunere in factori:
for(int i=2;i<=n;i+=2)
dp[i][++dp[i][0]]=2;
for(int i=3;i<=n;i+=2)
if(dp[i][0]==0)
for(int j=i;j<=n;j=j+i)
dp[j][++dp[j][0]]=i;
//pinex:
for(int i=m+1;i<=n;i++)
ans+=pinex(m,i);
printf("%lld\n",ans);
return 0;
}