题目描述
输入两个正整数n和k，求与n互质的第k个正整数。
输入输出格式
输入格式：
仅一行，为两个正整数n(≤10^6)和k(≤10^8)。
输出格式：
一个正整数，表示与n互质的第k个正整数。
输入输出样例
输入样例#1：
10 5
输出样例#1：
11
#include<cstdio> int a[1000006]; int gcd(int x,int y) { if(y==0)return x; else return gcd(y,x%y); } int main() { int n,k,num=0; scanf("%d%d",&n,&k); a[0]=n-1; for(int i=1;i<n;++i) if(gcd(i,n)==1)a[++num]=i; printf("%d ",(k-1)/num*n+a[k%num]); return 0; }