自动搬运

查看原文

来自洛谷，原作者为

	Weng_Weijie やー！今日もパンがうまい！

搬运于2025-08-24 21:59:20，当前版本为作者最后更新于2018-03-28 19:42:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

显然将$N$分解因数之后能得到$p,q$，然后就能算出$r,d,n$

所以这题的难点就在于如何分解因数，这里用到了Pollard rho算法

Pollard rho 算法原理：

生成一个随机数$x_1$, 判断$x_1$能否整除$N$, 如果不能，那么继续由$x_1$生成下一个$x_2$，已知循环做下去，必定构成一个环，形状类似一个$\rho$，所以叫Pollard rho算法

Pollard rho 算法流程 (注:2至6均在模$N$意义下)：

1. 判断$N$是否为质数，若是质数直接退出
2. 随机一个$x$和常数$c$
3. 令$y=x$
4. 令$x=x^2+c,d=\gcd(x-y,n)$
5. 重复执行4，直到$x=y$或$d|n$且$0<d<n$
6. 若$x=y$那么重新从1开始执行
7. 继续递归分解$d$和$\frac{n}{d}$

之后得到$N = pq$，之后剩余的就轻松解决了

代码如下

#include <stdio.h>
#include <stdlib.h>

#define int long long

int e, N, c, d, n, r;
//计算x,y的积
inline int mul(int x, int y, int c) {
	x %= c, y %= c; int r = 0;
	while (y) {
		if (y & 1) {r = r + x; if (r >= c) r -= c; }
		x = x + x; if (x >= c) x -= c; y = y >> 1;
	}
	return r;
}
//计算x的y次方
inline int pow(int x, int y, int c) {
	x %= c; int r = 1;
	while (y) {
		if (y & 1) r = mul(r, x, c); x = mul(x, x, c);
		y >>= 1;
	}
	return r;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
//求逆元
void exgcd(int a, int b, int &x, int &y) {
	if (!b) x = 1, y = 0;
	else {
		exgcd(b, a % b, y, x);
		y = (r + y - mul(a / b, x, r)) % r;
	}
}
//pollard rho算法
int pollard(int n, int c) {
	int x, y, d, i = 1, k = 2;
	x = 1LL * rand() * rand() % (n - 1) + 1;
	y = x;
	while (1) {
		x = (mul(x, x, n) + c) % n;
		d = gcd((x - y + n) % n, n);
		if (d > 1 && d < n) return d;
		if (x == y) return n;
        // x=y说明构成了一个环，说明选定的c不好，那么重新来一遍
		if (++i == k) k <<= 1, y = x; 
        // 由于y不一定在环内，所以随时更新y的值，不然会死循
	}
	return 23333333;
}

int tmp;
signed main() {
	signed x; srand(x);

	scanf("%lld%lld%lld", &e, &N, &c);
	int p = N;
	while (p >= N) p = pollard(N, 1LL * rand() * rand() % (n - 1) + 1);
	r = (p - 1) * (N / p - 1); exgcd(e, r, d, tmp);
	printf("%lld %lld\n", d, pow(c, d, N));
	return 0;
}