865
POJ 2773 歐拉函數
題意：讓求從1開始第k個與m互素的數。
求最大公約數的第一步是用大數對小數取餘。gcd(a,b)==gcd(a%b,b)，進一步推出gcd(a,b)==gcd(a+b, b)。也就是說，當求出了1~m間與m互質的數之後，把這些數加上m就可以得到m~2m間的與m互質的數。而且m~2m間不會有某個與m互質的數被漏掉。因為如果m<=a<=2m，且gcd(a, m)==1，那麼gcd(a - m, m)必然等於1。也就是必然有個在1~m間的數a-m，可以通過加m的方式得到a。所以與m互質的數是有周期性的。我們隻需要求出第一個周期即可。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long phi(long long n)
{
long long rea=n;
for(int i=2; i*i<=n; i++)
if(n%i==0)
{
rea=rea-rea/i;
do
n/=i;
while(n%i==0);
}
if(n>1)
rea=rea-rea/n;
return rea;
}
long long gcd(long long a,long long b)
{
if(!b)
return a;
return gcd(b,a%b);
}
int main()
{
long long m,k,ans;
while(~scanf("%I64d%I64d",&m,&k))
{
if(m==1)
{
printf("%I64d\n",k);
continue;
}
int b=phi(m),now=k/b;
if(k%b==0)now--;
for(long long i=now*m,num=0; i<(now+1)*m; i++)
{
if(gcd(i,m)==1)
num++;
if(num+now*b==k)
{
ans=i;
break;
}
}
printf("%I64d\n",ans);
}
return 0;
}
最後更新：2017-04-03 21:13:14