题意： 求与m互质的第k个数。
我们可以找到规律，
1 ，2 ，3 ，4， 5， 6 ，7，8,9, 11，12,13,14 与5互质的数 x*m + 小于5与互质的数。
gcd（b×t+a，b）=gcd（a，b） （t为任意整数）
则如果a与b互素，则b×t+a与b也一定互素，如果a与b不互素，则b×t+a与b也一定不互素
故与m互素的数对m取模具有周期性
所以把小于m与m互质的数标记出来即可。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
#define FF freopen("Input.txt","r",stdin)
#define Debug puts("I'm here")
#define mem(x,y) memset(x,y,sizeof(x))
const int N=1e6+100;
int prime[100000];//保存1000以内的素数
int num; //素数的个数
int isprime[N];
int flag[N]; //flag[i]表示i是否与当前m互质
inline void get_prime() //筛出素数
{
int i,j;
for(i=2;i<N;i++)
{
if(isprime[i]==0) prime[num++]=i;
for(j=0;j<num&&prime[j]*i<N;j++)
{
isprime[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
}
inline int euler(int n)//欧拉函数求出与m互质的总个数，并标记与m不互质的数。
{
int res=n;
int m=n;
for(int i=0;i<num&&prime[i]*prime[i]<=n;i++)
{
if(n%prime[i]==0)
{
res=res/prime[i]*(prime[i]-1);
while(n%prime[i]==0) n/=prime[i];
for(int j=prime[i];j<=m;j+=prime[i])
flag[j]=1;
}
}
if(n>1)
{
res=res/n*(n-1);
for(int j=n;j<=m;j+=n)
flag[j]=1;
}
return res;
}
inline int Find(int k)
{
int cnt=0;
for(int i=1;i<N;i++)
{
if(flag[i]==0)
cnt++;
if(cnt==k)
return i;
}
}
int main()
{
int m,k,i;
get_prime();
while(~scanf("%d%d",&m,&k))
{
mem(flag,0);
int len=euler(m);
int x,y;
y=k%len;
if(y==0) y=len;
x=k%len==0?k/len-1:k/len;
printf("%I64d\n",(__int64)(m*x+Find(y)));
}
return 0;
}
法二：用容斥求【1，mid】的内与m不互质的数的和，二分枚举mid。
先预处理出m的质因子。
容斥：集合中所有数 - 1个质因子 + 2个质因子乘积的 - 3个质因子乘积的+4个质因子乘积的 -、、、、、、。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=20;
int a[N],num,mid,sum;
void dfs(int i,int w,int flag)//容斥原理.
{
for(;i<num;i++)
{
int p=a[i]*w;
sum+=flag*(mid/p);
dfs(i+1,p,-flag);
}
return ;
}
int main()
{
int m,k;
while(~scanf("%d%d",&m,&k))
{
if(m==1)
{
printf("%d\n",k);
continue;
}
num=0;
for(int i=2;i<=m;i++) //求出所有质因子
{
if(m%i==0)
{
a[num++]=i;
while(m%i==0) m/=i;
if(m==1) break;
}
}
if(m>1) a[num++]=m;
int l=1,r=0x7fffffff,ans=0;
while(l<=r)//二分枚举
{
mid=(l+r)>>1;
sum=0;
dfs(0,1,1);
sum=mid-sum;
if(sum>=k)
{
r=mid-1;
if(sum==k) ans=mid;//不能break，
}
else l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}