【模板】有理数取余

_H17_ · 2025-03-06 22:37:43 · 题解

题目分析

设 p=19260817。

需要求 \frac{a}{b}\bmod p。

根据余数的可乘性，题目变为 [(a\bmod p)\times (\frac{1}{b}\bmod p)]\bmod p。

瓶颈在于求 \frac{1}{b}\bmod p。

我们假设这个数是 x。

根据余数的可乘性，b\times x \equiv 1\pmod{p}。

根据费马小定理，当 b,p 互质，且 p 是质数的时候，b^{p-1}\equiv 1\pmod{p}（判一下就一个 p 是质数）。

变形之后就是 b\times b^{p-2}\equiv 1\pmod{p}。

所以上面的最原始的同余方程得到 x=b^{p-2}\bmod p 是一个整数解。

这样这个题也就迎刃而解了。

代码实现

#include<bits/stdc++.h>
//#define int long long 
using namespace std;
const int mod=19260817;
int a,b;
int qp(int a,int b){
    int ret=1;
    a%=mod;
    while(b){
        if(b&1)
            ret*=a,ret%=mod;
        a*=a,a%=mod,b>>=1;
    }
    return ret;
}
void read(int&a){
    a=0;
    char c;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9'){
        a=a*10%mod+(c-48),a%=mod,c=getchar();
    }
    return;
}
signed main(){
    read(a),read(b);
    cout<<(a%mod*qp(b,mod-2))%mod;
    return 0;
}