专栏文章

UVA12799 题解

MMasterArcherSkeleton
UVA12799题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipudaep
此快照首次捕获于
2025/12/03 18:05
3 个月前
此快照最后确认于
2025/12/03 18:05
3 个月前
查看原文

题意简述

选出两个不相等的奇质数 p,qp,q，令 n=pqn = pq，算出 φ(n)=(p−1)(q−1)\varphi(n) = (p - 1)(q - 1)，选出整数 e(1≤e<φ(n),gcd⁡(e,φ(n))=1)e(1 \le e < \varphi(n),\gcd(e, \varphi(n)) = 1)，再算出 ee 在模 φ(n)\varphi(n) 意义下的逆元 d(1≤d<φ(n))d(1 \le d < \varphi(n))。现有多组数据，每组数据给出整数 n,e,c(15≤n≤109,1≤e,c≤n)n, e, c(15 \le n \le 10^9, 1 \le e, c \le n)，求出每组数据对应的 m=cd mod nm = c^d \bmod n。
最后给出题目地址 UVA12799 RSA。

正解思路

这道题的每组数据需要做三件事。

一、求出 φ(n)\varphi(n)

按照题意，φ(n)=(p−1)(q−1)\varphi(n) = (p - 1)(q - 1)，不妨 p<qp < q，又有 n=pqn = pq，所以一定有 p<np < \sqrt{n}，并且 q=npq = \frac{n}{p}。所以，可以从 11 到 ⌊n⌋\lfloor \sqrt{n} \rfloor 枚举 pp（显然，这样的 pp 只有一个）。找到后，求出 q=npq = \frac{n}{p}，进而求出 φ(n)=(p−1)(q−1)\varphi(n) = (p - 1)(q - 1)。
时间复杂度：O(n)\Omicron(\sqrt{n})。

二、求出 ee 在模 φ(n)\varphi(n) 意义下的逆元 dd

由题意，de≡1(modn)de \equiv 1 \pmod n。那么，已知 ee 与 nn，如何求出 dd 呢？
有一种方法，根据欧拉定理，因为 gcd⁡(d,φ(n))=1\gcd(d, \varphi(n)) = 1，所以可以求出 d=eφ(φ(n))−1d = e^{\varphi(\varphi(n)) - 1}（求 φ\varphi 函数的方法就用模板即可，求幂方法同【三、求出 cd mod nc^d \bmod n】中的方法）。虽然这种方法的时间复杂度是 O(n+log⁡2n)=O(n)\Omicron(\sqrt{n} + \log_2 n) = \Omicron(\sqrt{n})，足以通过此题，但是其实有一种更优的方法（拓展欧拉定理），在这里介绍一下。
首先，因为 de≡1(modn)de \equiv 1 \pmod n，所以有 de+nt=1(t∈Z)de + nt = 1(t \in \Z)。
注意到，若有一方程 a0x0+b0y0=gcd⁡(a0,b0)a_0x_0 + b_0y_0 = \gcd(a_0, b_0)，其中 a0,x0,b0∈Na_0, x_0, b_0 \in \N，y0∈Zy_0 \in \Z，且 a0,x0<b0a_0, x_0 < b_0。则令 a0=e,b0=na_0 = e, b_0=n，有 gcd⁡(a0,b0)=gcd⁡(e,n)=1\gcd(a_0, b_0) = \gcd(e, n) = 1，则解出的 x0x_0 就是 a0a_0 在模 b0b_0 意义下的逆元，即 ee 在模 nn 意义下的逆元。
那么怎么解出这个方程呢？其实最开始的方程的右边是 gcd⁡(a0,b0)\gcd(a_0, b_0)，只是因为我们代入的值使其为 11。我们想到，可否使用类似于求最大公因数的方法来求解这个方程呢？
若有 i∈Ni \in \N，且 bi≠0b_i \ne 0，则令 ai+1=bi,bi+1=ai mod bia_{i + 1} = b_i,b_{i + 1} = a_i \bmod b_i，得到一个新的方程 ai+1xi+1+bi+1yi+1=gcd⁡(a0,b0)a_{i+1}x_{i+1} + b_{i+1}y_{i+1} = \gcd(a_0,b_0)（因为 gcd⁡(ai+1,bi+1)=gcd⁡(ai,bi)\gcd(a_{i+1},b_{i+1}) = \gcd(a_i,b_i)）。直到 bi=0b_i = 0，令此时的 ii 为 kk。那接下来就需要依次求出 i≤ki \le k 时，xi,yix_i,y_i 的解。
然而正常情况下这样的方程的解应该不止一个，但是在我们要求的问题中，若 i<ki < k，显然 xix_i 的不同解都在同一个模 bib_i 的剩余类上，每个 xix_i 的解都对应出一个 yiy_i，所以在要求 0≤xi<bi0 \le x_i < b_i 的情况下，显然有 xix_i 唯一；否则，即 i=ki = k，此时 ai=gcd⁡(a0,b0),bi=0a_i = \gcd(a_0,b_0),b_i = 0，所以 gcd⁡(a0,b0)xk+0⋅yk=gcd⁡(a0,b0)\gcd(a_0,b_0)x_k + 0 \cdot y_k = \gcd(a_0,b_0)，即 xk=gcd⁡(a0,b0)gcd⁡(a0,b0)=1x_k = \frac{\gcd(a_0,b_0)}{\gcd(a_0,b_0)} = 1，而 yky_k 可取任意值。当然，在我们所求的问题中，yky_k 取何值都没关系，不妨 yk=0y_k = 0。
那么，若已知 xi+1,yi+1(0≤i<k)x_{i+1},y_{i+1}(0 \le i < k)，如何求出 xix_i 与 yiy_i 呢？显然，ai+1=bi,bi+1=ai mod bia_{i + 1} = b_i,b_{i + 1} = a_i \bmod b_i。令 r=⌊aibi⌋r = \lfloor \frac{a_i}{b_i} \rfloor，则 bi+1=ai−r⋅bib_{i+1} = a_i - r \cdot b_i。代入 ai+1xi+1+bi+1yi+1=gcd⁡(a0,b0)a_{i+1}x_{i+1} + b_{i+1}y_{i+1} = \gcd(a_0,b_0)，得：bixi+1+(ai−r⋅bi)yi+1=gcd⁡(a0,b0)b_ix_{i+1} + (a_i - r \cdot b_i)y_{i+1} = \gcd(a_0,b_0)。即：aiyi+1+bi(xi+1−r⋅yi+1)=gcd⁡(a0,b0)a_iy_{i+1} + b_i(x_{i+1}-r \cdot y_{i+1}) = \gcd(a_0,b_0)。所以：xi=yi+1,yi=xi+1−r⋅yi+1=xi+1−⌊aibi⌋⋅yi+1x_i = y_{i+1},y_i = x_{i+1} - r \cdot y_{i+1} = x_{i + 1} - \lfloor \frac{a_i}{b_i} \rfloor \cdot y_{i+1}。
这样，只要利用类似于求最小公约数的方法求出上面方程中令 a0=d,b0=φ(n)a_0 = d,b_0=\varphi(n) 的一组解中的 x0x_0 并将其转换为与其同余的大于等于 00 小于模数 b0b_0 的整数即可求出 ee 在模 φ(n)\varphi(n) 意义下的逆元 dd。
时间复杂度：O(log⁡2n)\Omicron(\log_2 n)。
但是这里有一个细节，那就是最后取模的时候得出的 x0x_0 可能是负数，所以一定要记得判断正负性，因为在 C++ 中，是不能直接对负数取模的。所以，假设已经算出 φ(n)\varphi(n) 并将其存储至变量 rr 中，则如果要让 xx 对 rr 取模，不能写成 x = x % r;，而要写成 x = (x >= 0) ? (x % r) : ((r - (-x) % r) % r)（码风不好，见谅，懂意思就行）。

三、求出 cd mod nc^d \bmod n

好了，接下来就是求出 m=cd mod nm = c^d \bmod n 并输出了（显然，d≥1d \ge 1）。但是注意到 n≤109n \le 10^9。那么，如果按照下面代码片段的方法求 cd mod nc^d \bmod n 的话，是肯定会超时的（因为时间复杂度是 O(d)=O(n)\Omicron(d) = \Omicron(n)）：
CPP
long long s = 1;
for(int i = 1; i <= d; i ++) {
    s = s * c % n;
}
return s;
所以，需要进行优化。
这里需要用到分治或倍增的思想（有两种实现方式）。

分治法

令 f(x)=cx mod n(x∈N∗)f(x) = c^x \bmod n(x \in \N^*)。显然当 x>1x > 1 时，有：
f(x)=cx mod n=c2⌊x2⌋+x mod 2 mod n=((c⌊x2⌋)2⋅cx mod 2) mod n=(f(⌊x2⌋)2⋅cx mod 2) mod n\begin{aligned} f(x) &= c^x \bmod n \\ &= c^{2 \lfloor \frac{x}{2} \rfloor + x \bmod 2} \bmod n \\ &= ((c^{\lfloor \frac{x}{2} \rfloor})^2 \cdot c^{x \bmod 2}) \bmod n \\ &= (f(\lfloor \frac{x}{2} \rfloor)^2 \cdot c^{x \bmod 2}) \bmod n \end{aligned}
所以：
f(x)={cx=1(f(⌊x2⌋)2⋅cx mod 2) mod nx>1f(x) = \begin{cases} c & x = 1 \\ (f(\lfloor \frac{x}{2} \rfloor)^2 \cdot c^{x \bmod 2}) \bmod n & x > 1 \end{cases}
所以就可以用上面方法递归求出 f(d)f(d) 的值，即 cd mod nc^d \bmod n 的值。时间复杂度：O(log⁡2d)=O(log⁡2n)\Omicron(\log_2 d) = \Omicron(\log_2 n)。

倍增法

因为 d∈N∗d \in \N^*，所以显然存在正整数 kk，以及正整数 w0,w1,⋯ ,wk−1(wk−1≠0)w_0,w_1,\cdots,w_{k-1}(w_{k-1} \ne 0)，且对于所有的 i∈Ni \in \N 并且 i<ki < k 都有 wi∈{0,1}w_i \in \{0,1\}，并满足 d=∑i=0k−12iwid = \sum_{i=0}^{k-1} 2^i w_i。所以：
cd=c∑i=0k−12iwi=∏i=0k−1c2iwi=∏i=0k−1(c2i)wi\begin{aligned} c^d &= c^{\sum_{i=0}^{k-1} 2^i w_i} \\ &= \prod_{i=0}^{k-1} c^{2^i w_i} \\ &= \prod_{i=0}^{k-1} (c^{2^i})^{w_i} \end{aligned}
显然，若 i∈Ni \in \N，则：
c2i={ci=0(c2i−1)2i>0c^{2^i} = \begin{cases} c & i = 0 \\ (c^{2^{i-1}})^2 & i > 0 \end{cases}
所以，用一个变量存储答案（初值为 11），从小（00）到大（k−1k - 1）循环枚举整数 ii：每次按照上面方法求出 c2i mod nc^{2^i} \bmod n，如果 wi=1w_i = 1，则让答案变量乘上 c2i mod nc^{2^i} \bmod n 后对 nn 取模。显然，k=⌊log⁡2n⌋+1k = \lfloor \log_2 n \rfloor + 1。所以时间复杂度也是 O(log⁡2n)\Omicron(\log_2 n)。
所以，正解思路总的时间复杂度就是 O(tn)\Omicron(t \sqrt{n})（tt 表示询问总数）。

代码

在放代码之前，我想说一些细节：
  1. 记得开 long long！！
  2. 注意是多组数据，想好读入方式。
好了，接下来放代码。

分治法

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, e, c, r, x, y;
int Phi(int t) {//这道题情况比较特殊，不用打全求欧拉函数的模板 
	for(int i = 2; ; i ++) {
		if(t % i == 0) {
			return (i - 1) * (t / i - 1);
		}
	}
}
void Exgcd(int a, int b) {//拓展欧拉定理求逆元 
	if(!b) {
		x = 1;
		y = 0;
		return; 
	}
	Exgcd(b, a % b);
	int temp = y;
	y = x - (a / b) * y;
	x = temp;
}
int Quick_pow(int t) {
	if(t == 1) return c;
	int tmp = Quick_pow(t >> 1);
	(tmp *= tmp) %= n;
	if(t & 1) (tmp *= c) %= n;
	return tmp;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//读入小优化，不介意吧 
	while(cin >> n >> e >> c) {
		r = Phi(n);
		Exgcd(e, r);
		cout << Quick_pow((x >= 0) ? (x % r) : ((r - (-x) % r) % r)) << endl;
	}
	return 0;
}

倍增法

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, e, c, r, x, y;
int Phi(int t) {//这道题情况比较特殊，不用打全求欧拉函数的模板 
	for(int i = 2; ; i ++) {
		if(t % i == 0) {
			return (i - 1) * (t / i - 1);
		}
	}
}
void Exgcd(int a, int b) {//拓展欧拉定理求逆元 
	if(!b) {
		x = 1;
		y = 0;
		return; 
	}
	Exgcd(b, a % b);
	int temp = y;
	y = x - (a / b) * y;
	x = temp;
}
int Quick_pow(int t) {
	int tmp = c, s = 1;
	while(t) {
		if(t & 1) (s *= tmp) %= n;
		(tmp *= tmp) %= n;
		t >>= 1;
	}
	return s;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//读入小优化，不介意吧 
	while(cin >> n >> e >> c) {
		r = Phi(n);
		Exgcd(e, r);
		cout << Quick_pow((x >= 0) ? (x % r) : ((r - (-x) % r) % r)) << endl;
	}
	return 0;
}

提交记录

分治法提交记录
倍增法提交记录

总结

本题思路较为简单，只是需要一些数论的知识，照题意模拟即可。代码比较短，自己手打。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...