题目描述
输入两个正整数n和k，求与n互质的第k个正整数。
输入输出格式
输入格式：
仅一行，为两个正整数n(≤10^6)和k(≤10^8)。
输出格式：
一个正整数，表示与n互质的第k个正整数。
由于当a与b互质时，a+b与b互质，可以求出a以内的互质的数，由周期性推出剩下所有的与a互质的数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=1000005,INF=2000000000;
int coprime[maxn],copri=0; int gcd(int a,int b) {return b==0 ? a:gcd(b,a%b);} int main()
{
int N,K;
cin>>N>>K;
coprime[0]=-1;
for(int i=1;i<N;i++) if(gcd(N,i)==1) coprime[++copri]=i;
cout<<K/copri*N+coprime[K%copri]<<endl;
return 0;
}