【模板】有理数取余

1. 大数取模

利用取模的性质：

(A \times 10 + B) \pmod P = ((A \pmod P \times 10) \pmod P + B \pmod P) \pmod P

这是一道数论题目，主要考查以下两个知识点：

大数取模（读入优化）：如何处理超长数字的取模。
模运算下的除法（乘法逆元）：在模运算中，除以一个数等于乘以这个数的逆元。

下面我们分步拆解这道题的解法。

2. 核心: 逆元,费马小定理

题目要求计算 $c = \frac{a}{b} \pmod{P}$ ，其中 $P = 19260817$ 。

在模运算中，除法不能直接做，需要转化为乘法：

\frac{a}{b} \equiv a \times b^{-1} \pmod P

这里的 $b^{-1}$ 指的是 $b$ 在模 $P$ 意义下的乘法逆元。

如何求逆元？

首先，我们需要知道模数 $P = 19260817$ 是一个质数。

根据费马小定理：若 $P$ 是质数，且 $b$ 不是 $P$ 的倍数（即 $b \not\equiv 0 \pmod P$ ），则有：

b^{P-1} \equiv 1 \pmod P

变形一下：

b \times b^{P-2} \equiv 1 \pmod P

根据逆元的定义（ $b \times b^{-1} \equiv 1$ ），我们可以得出：

b^{-1} \equiv b^{P-2} \pmod P

代码

cpp

#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
typedef long long ll;
ll mod = 19260817; 

ll read() {
    ll x = 0;
    char c = getchar();
    while (c < '0' || c >'9')  c = getchar();

    while (c >= '0' && c <= '9') {
        x = ( x * 10 + (c -'0')) % mod;
        c = getchar();
    }
    return x;
}

ll quick_pow(ll base,ll n) {
    ll res =1;
    for(ll i = n; i>0 ; i >>=1)
    {
        if( i & 1 ) {
            res *= base;
            res %= mod;
        }
        base = base *base % mod;
    }

    return res;
}

int main() {
    ll a = read();
    ll b = read();

    //  判断是否有解
    if (b == 0) {
        // 如果 b % MOD 为 0，说明 b 是 19260817 的倍数。
        // 根据题目保证 "a, b 不同时是倍数"，此时 a一定不为0。
        // 0 * x = a (mod P) 无解。
        cout << "Angry!" << endl;
    }
    else {
        // 4. 计算答案
        // 答案 = a * b的逆元 % MOD
        // b的逆元 = b^(MOD-2) % MOD (费马小定理)
        long long inv_b = quick_pow(b, mod - 2);
        long long ans = (a * inv_b) % mod;
        cout << ans << endl;
    }
    

    return 0;
}

总结关键点：

模数性质： $19260817$ 是质数，这是使用费马小定理求逆元的前提。
大数读入：不需要高精度库，只需要在读入字符时利用秦九韶算法原理（x = x*10 + c）并时刻取模。
逆元公式： $\frac{a}{b} \pmod P \iff a \times b^{P-2} \pmod P$ 。

【模板】有理数取余

目录

1. 大数取模

2. 核心: 逆元,费马小定理

代码

总结关键点：