信奥赛C++提高组csp-s之数论基础专题课：从同余到分数模运算7(案例实践：分数模运算)

信奥赛C++提高组csp-s之数论基础专题课：从同余到分数模运算7(案例实践：分数模运算)

课程目标

第三部分：案例实战（分数模运算）

研究案例：P2613 有理数取余

题目描述

给出一个有理数

c

=

a

b

c=\\frac{a}{b}

c=ba​，求

c
 

m

o

d

19260817

c \\bmod 19260817

cmod19260817 的值。

这个值被定义为

b

x

≡

a

(

m

o

d

19260817

)

bx\\equiv a\\pmod{19260817}

bx≡a(mod19260817) 的解。

输入格式

一共两行。

第一行，一个整数

a

a

a。 第二行，一个整数

b

b

b。

输出格式

一个整数，代表求余后的结果。如果无解，输出 Angry!。

输入输出样例 1

输入 1

233
666

输出 1

18595654

说明/提示

对于所有数据，保证

0

≤

a

≤

10

10001

0\\leq a \\leq 10^{10001}

0≤a≤1010001，

1

≤

b

≤

10

10001

1 \\leq b \\leq 10^{10001}

1≤b≤1010001，且

a

,

b

a, b

a,b 不同时是

19260817

19260817

19260817 的倍数。

思路分析

一、题目重述与理解

题目要求计算有理数

c

=

a

b

c = \\frac{a}{b}

c=ba​ 对模数 19260817 取余的值。这里的“有理数取余”并不是直接对分数进行除法，而是定义为同余方程

b

x

≡

a

(

m

o

d

19260817

)

b x \\equiv a \\pmod{19260817}

bx≡a(mod19260817) 的解 x 。也就是说，我们需要找到一个整数 x ，使得 b x 和 a 在模 19260817 的意义下相等。

输入给出两个整数 a 和 b ，它们都是长度可达 10001 位的十进制大整数，因此不能直接用常规的整型存储。输出为计算得到的 x 值（范围在 0 到 19260816 之间），如果无解则输出 Angry!。

题目的数据范围保证了 a 和 b 不会同时是模数 19260817 的倍数，这为无解判定提供了依据。

二、数学原理

1. 同余方程与模逆元

方程

b

x

≡

a

(

m

o

d

M

)

b x \\equiv a \\pmod{M}

bx≡a(modM)（其中 M = 19260817 ）是一个线性同余方程。当 b 与模数 M 互质时，方程有唯一解，解为

x

≡

a

⋅

b

−

1

(

m

o

d

M

)

,

x \\equiv a \\cdot b^{-1} \\pmod{M},

x≡a⋅b−1(modM), 其中

b

−

1

b^{-1}

b−1 是 b 模 M 的乘法逆元，即满足

b

⋅

b

−

1

≡

1

(

m

o

d

M

)

b \\cdot b^{-1} \\equiv 1 \\pmod{M}

b⋅b−1≡1(modM) 的整数。

当 b 与 M 不互质时，方程可能无解或有多解。具体地，若

gcd

⁡

(

b

,

M

)

∤

a

\\gcd(b, M) \\nmid a

gcd(b,M)∤a，则无解；若

gcd

⁡

(

b

,

M

)

∣

a

\\gcd(b, M) \\mid a

gcd(b,M)∣a，则方程有

gcd

⁡

(

b

,

M

)

\\gcd(b, M)

gcd(b,M) 个解。但由于本题的特殊性，我们实际上只需判断

b
 

m

o

d

M

=

0

b \\bmod M = 0

bmodM=0 的情况，因为题目保证 a 和 b 不同时是 M 的倍数，所以当

b

≡

0

(

m

o

d

M

)

b \\equiv 0 \\pmod{M}

b≡0(modM) 时必有

a

≢

0

(

m

o

d

M

)

a \\not\\equiv 0 \\pmod{M}

a≡0(modM)，此时

g

c

d

(

b

,

M

)

=

M

gcd(b, M) = M

gcd(b,M)=M 显然不整除 a （除非 a 也是 M 的倍数，但被排除），因此无解。

2. 模数的性质

模数 M = 19260817 是一个质数（可通过简单检验或查证得知）。因此对于任意

b

≢

0

(

m

o

d

M

)

b \\not\\equiv 0 \\pmod{M}

b≡0(modM)，都有

gcd

⁡

(

b

,

M

)

=

1

\\gcd(b, M) = 1

gcd(b,M)=1，即 b 在模 M 下存在唯一的逆元。这使得我们可以利用费马小定理来求逆元。

3. 费马小定理求逆元

费马小定理指出：若 p 是质数，且 b 不是 p 的倍数，则

b

p

−

1

≡

1

(

m

o

d

p

)

.

b^{p-1} \\equiv 1 \\pmod{p}.

bp−1≡1(modp). 两边同时除以 ( b )（即乘以 ( b ) 的逆元），得到

b

p

−

2

≡

b

−

1

(

m

o

d

p

)

.

b^{p-2} \\equiv b^{-1} \\pmod{p}.

bp−2≡b−1(modp). 因此，我们可以通过快速幂计算

b

p

−

2

m

o

d

p

b^{p-2} \\bmod p

bp−2modp 来得到 b 的逆元，时间复杂度为

O

(

log

⁡

p

)

O(\\log p)

O(logp)。

三、大整数取模技巧

由于 a 和 b 可能长达 10001 位，无法直接读入整型变量。常用的处理方法是：用字符串读入，然后逐位计算其对 M 的模。设字符串 s 表示的数为

d

k

d

k

−

1

…

d

0

d_k d_{k-1} \\dots d_0

dk​dk−1​…d0​（十进制），则

val

=

(

⋯

(

(

d

k

×

10

+

d

k

−

1

)

×

10

+

⋯
 

)

×

10

+

d

0

)
 

m

o

d

M

.

\\text{val} = ( \\cdots ((d_k \\times 10 + d_{k-1}) \\times 10 + \\cdots ) \\times 10 + d_0 ) \\bmod M.

val=(⋯((dk​×10+dk−1​)×10+⋯)×10+d0​)modM. 在每一步中，我们都可以取模，防止中间结果溢出。具体实现：

int str_mod(const string &s) {
long long res = 0;
for (char c : s) {
res = (res * 10 + (c – '0')) % MOD;
}
return res;
}

这种方法可以安全地将任意长的十进制数转化为模 M 下的值。

四、无解情况的判定

根据题目给出的条件：“( a, b ) 不同时是 ( 19260817 ) 的倍数”。因此：

• 如果 $b\mathrm{mod}M=0$
• 代入方程：$0\cdot x\equiv a(\mathrm{mod}M)$

反之，若

b
 

m

o

d

M

≠

0

b \\bmod M \\neq 0

bmodM=0，则 b 与 M 互质（因为 M 是质数），方程有唯一解。

五、算法步骤与复杂度

算法步骤

复杂度分析

• 读入并取模：遍历两个字符串，每个字符处理一次，时间复杂度 $O(\text{len}(a)+\text{len}(b))$
• 快速幂：计算 $b^{\prime M-2}\mathrm{mod}M$
• 总时间复杂度：$O(\text{len}(a)+\text{len}(b)+\log M)$

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 19260817;

// 快速幂函数：计算 a^b % MOD
int qpow(long long a, int b) {
long long res = 1;
while (b) {
if (b & 1) res = res * a % MOD; // 若当前二进制位为1，乘上a
a = a * a % MOD; // a自乘，准备下一位
b >>= 1; // 右移一位
}
return res;
}

// 将大整数字符串转换为模 MOD 下的值
int str_mod(const string &s) {
long long r = 0;
for (char c : s) {
r = (r * 10 + (c – '0')) % MOD; // 逐位取模，防止溢出
}
return r;
}

int main() {
string sa, sb; // 用字符串读入大整数 a 和 b
cin >> sa >> sb;

int a = str_mod(sa); // a 在模 MOD 下的值
int b = str_mod(sb); // b 在模 MOD 下的值

if (b == 0) { // 若 b 是 MOD 的倍数，则方程无解
cout << "Angry!" << endl;
} else {
int inv_b = qpow(b, MOD – 2); // 用费马小定理求逆元
int ans = (long long)a * inv_b % MOD; // 计算最终结果
cout << ans << endl;
}
return 0;
}

功能分析

• 大整数取模：利用 str_mod 函数，在读入字符串的过程中不断进行 (r*10 + digit) % MOD 运算，将任意长度的大整数安全地映射到 [0, MOD-1] 范围内。
• 无解判断：若 b % MOD == 0，则原方程左侧为 0，右侧 a % MOD 必不为 0（题目保证不同时为 MOD 的倍数），故直接输出 "Angry!"。
• 逆元求解：利用费马小定理和快速幂，在 O(log MOD) 时间内求出 b 的逆元。
• 结果计算：将 a 与逆元相乘后再取模，得到最终的答案。

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》： https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html

4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}