自动搬运

查看原文

来自洛谷，原作者为

	Drifterming 这个家伙很勤，留下了一句个签。

搬运于2025-08-24 21:26:51，当前版本为作者最后更新于2018-05-13 21:13:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

//可以发现一个事情
//比如和10互质的数
//1,3,7,9,11,13,17,19,21,23,27,29
//我们可以把它们分成好几部分
//1,3,7,9,   11,13,17,19,   21,23,27,29 
//可以发现，他们的个位数都是一样的
//也就是说，我们可以求出φ(n)，也就是n的欧拉函数值 
//φ(n)就是周期的长度
//那么，我们可以利用这个周期的规律来输出
//把与<n的与n互质的数给存下来
//然后输出 (k-1)/cnt*n+a[(k-1)%cnt+1]
//什么意思呢，(k-1)/cnt找的是第k个数在第几个周期里，+a[(k-1)%cnt+1]就是找对应的数 

//其实它是利用了一个性质：
//if gcd(a,b)==1
//then gcd(a+b,b)==1
//为什么呢。
//设gcd(a,b)=c,
//那么存在互质m,n,使得a=mc,b=nc. (要不然gcd(a,b)就==c*gcd(m,n)了) 
//a+b=(m+n)c
//因为m,n互质,m和n没有>1的共同的因子 
//所以m*n同样和m，n没有>1的共同的因子（质因数分解，很好理解，m*n的因子=m的因子∪n的因子 ） 
//所以m+n和m也是互质,
//由此gcd(a,a+b)=c=gcd(a,b) 
//所以gcd(a,ax+b)=c=gcd(a,b)  （x表示a的x倍，gcd里的mod就是把x给消掉）
//所以在ax~a(x+1)中，与a互质的个数等于<a的数中与a互质的b个数φ(a)
//所以在ax~a(x+1)中, 存在第φ(a)*x~φ(a)*(x+1)个与a互质的数
//所以如果求第k个和n互质的数
//可以算出φ(n)，让k/φ(n)算出x，然后让n*=x，再加上相应的b就是ans了 
//b就是<a的与a互质的数，把它们存下来 

//.....好啰嗦啊。。自己都看不太明白了 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=1e6+5;

int n,k;
int a[N],cnt;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;++i)
		if(__gcd(i,n)==1)
			a[++cnt]=i;
	printf("%d",(k-1)/cnt*n+a[(k-1)%cnt+1]);
	return 0;
}