云朵角落

外观

有理数取余

约 842 字大约 3 分钟

SolutionAlgorithm

2021-06-25

题目描述

P2613 【模板】有理数取余

题目非常简单易懂

给出一个有理数 c=abc=\frac{a}{b}，求 c mod 19260817c\bmod19260817 的值。

思路

看到这道题时

  • 第一眼：好像很简单啊
  • 第二眼：a,b≤1010001a,b\leq10^{10001}？！！
  • 第三眼：卧槽这啥玩意？！！

要做这道题，我们来介绍一个新的东西（主要是本蒟蒻不会exgcd（欧几里得扩展）

逆元

P 是一个质数

令 b′b' 为 bb 的逆元，那么有b×b′≡1 (mod P)b\times b'\equiv1\,(mod\,P)

有 ab≡ab×1≡ab×(b×b′)≡a×b′ (mod P)\frac{a}{b}\equiv\frac{a}{b}\times1\equiv\frac{a}{b}\times(b\times b')\equiv a\times b'\,(mod\,P)

显然可以看出 b′b' 的值为 1b\frac{1}{b}

但是除以 bb 与乘以 1b\frac{1}{b} 是一样的啊，怎么办呢？

费马小定理闪亮登场

定理内容：如果 pp 是一个质数，而整数 aa 不是 pp 的倍数，则有ap−1≡1 (mod p)a^{p-1}\equiv1\,(mod\,p)

证明

你可以选择跳过这部分

证明部分 pp 是一个质数

第一个证明

首先我们考虑一个前置定理：

若gcd(c,p)=1gcd(c,p)=1，且ac≡bc (mod p)ac\equiv bc\,(mod\,p)，那么有a≡b (mod p)a\equiv b\,(mod\,p)

证：

∵ac≡bc (mod p)∴(a−b)c≡0 (mod p)∴(a−b)c 是 p 的整数倍又∵gcd(c,p)=1∴a−b≡0 (mod p)即a≡b (mod p)\begin{align} &\because ac\equiv bc\,(mod\,p)\\ &\therefore (a-b)c\equiv 0\,(mod\,p)\\ &\therefore (a-b)c\,\text{是}\,p\,\text{的整数倍}\\ \text{又}&\because gcd(c,p)=1\\ &\therefore a-b\equiv0\,(mod\,p)\\ &\text{即}a\equiv b\,(mod\,p) \end{align}

证毕

第二个证明

然后我们进入正题，假设有正整数 a(a<p)a(a<p) 满足条件 gcd(a,p)=1gcd(a,p)=1，那么我们将 aa 乘上 1∼p−11\thicksim p-1 后可以构成一个 mod pmod\,p 的完全剩余系

证：

假设存在xa≡ya (mod p),且x≠y∵gcd(a,p)=1∴原式成立当且仅当x≡y (mod p)又∵x,y∈[1,p−1]∴x≡y (mod p)当且仅当x=y,与已知条件矛盾∴假设不成立，原命题成立\begin{align} &\text{假设存在}xa\equiv ya\,(mod\,p),\text{且}x\neq y\\ &\because gcd(a,p)=1\\ &\therefore \text{原式成立当且仅当}x\equiv y\,(mod\,p)\\ \text{又}&\because x,y\in [1,p-1]\\ &\therefore x\equiv y\,(mod\,p)\text{当且仅当}x=y,\text{与已知条件矛盾}\\ &\therefore \text{假设不成立，原命题成立} \end{align}

证毕

第三个证明

接下来证明 ap−1≡1 (mod p)a^{p-1}\equiv1\,(mod\,p)

证：

∵1,2,⋯ ,p−1是 mod p 的完全剩余系∴有1×2×⋯×p−1≡a×2a×⋯×(p−1)a (mod p)即(p−1)!≡(p−1)!×ap−1 (mod p)又∵p是质数∴gcd((p−1)!,p)=1∴ap−1≡1 (mod p)\begin{align} &\because 1,2,\cdots,p-1\text{是}\,mod\,p\,\text{的完全剩余系}\\ &\therefore\text{有}1\times2\times\cdots\times p-1\equiv a\times2a\times\cdots\times (p-1)a\,(mod\,p)\\ &\text{即} (p-1)!\equiv (p-1)!\times a^{p-1}\,(mod\,p)\\ \text{又}&\because p\text{是质数}\\ &\therefore gcd((p-1)!,p)=1\\ &\therefore a^{p-1}\equiv1\,(mod\,p) \end{align}

证毕

回归正题

根据费马小定理，显然 b′=bP−2b'=b^{P-2}

什么？不显然吗？

∵b′×b≡1 (mod P)bP−1≡1 (mod P)∴b′×b≡bP−1 (mod P)∴b′=bP−2\begin{align} \because b'\times b&\equiv1\,(mod\,P)\\ b^{P-1}&\equiv1\,(mod\,P)\\ \therefore b'\times b&\equiv b^{P-1}\,(mod\,P)\\ \therefore b'&=b^{P-2} \end{align}

那么 ab=a×bP−2\frac{a}{b}=a\times b^{P-2}

然后我们就可以用快速幂轻松 A 掉这题了（psps：虽然快速幂让我们不需要高精了，但long long还是要的

代码

#include<cstdio>

const int MOD = 19260817;

inline long long read() {
	long long X = 0, flag = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') flag = 0; ch=getchar();}
	while(ch >= '0' && ch <= '9') {X = (X * 10 + (ch ^ 48)) % MOD; ch = getchar();}
	return flag ? X : -X;
}

long long a, b;

long long QuickPow(long long x, long long y) {
	long long ans = 1, k = MOD - 2;
	while(k) {
		if(k & 1) ans = ans * x % MOD;
		x = x * x % MOD;
		k >>= 1;
	}
	return ans * y % MOD;
}//快速幂不建议这样写，还是用模板比较好

int main() {
	a = read(); b = read();
	if(b) printf("%lld\n", QuickPow(b, a));
	else printf("Angry!\n");
	return 0;
}

贡献者

Honahec

更新日志

2026/6/8 12:28
查看所有更新日志
  • 39436-update于
  • 36e18-Fixes LaTeX formatting于
  • 7ced7-Reuploads previous blogs于

版权归属：Honahec

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)