見：P2613 【模板】有理數取余 - 洛谷

題目描述

給出一個有理數?c=ba?，求?cmod19260817?的值。

這個值被定義為?bx≡a(mod19260817)?的解。

輸入格式

一共兩行。

第一行，一個整數?a。
第二行，一個整數?b。

輸出格式

一個整數，代表求余后的結果。如果無解，輸出?Angry!。

輸入輸出樣例

in：
233
666
out：
18595654

說明/提示

對于所有數據，保證?0≤a≤1010001，1≤b≤1010001，且?a,b?不同時是?19260817?的倍數。

算法介紹

本題需使用逆元。

逆元即對于同余方程?ax≡1(modp)，

則?x?為?amodp?的逆元，

記作?a?1。

若其滿足?a?p，

則?a?1≡ap?2(modp)。

本題中?a?和?b?為較大的整數，

可以用快讀來讀入，

并對?19260817?取模。

正確性證明

根據費馬小定理可知?ap?1≡1(modp)。

費馬小定理證明：

構造集合?S={1,2,3,…,p?1}，

同時構造集合?S′={a,a×2,a×3,…,a×(p?1)}。

由于?a?p，

所以?a?和?p?互質。

因此對于所有不同的?u?和?v，

一定滿足?a×u≡a×v(modp)。

所以?S′?是模?p?意義下的完全剩余系，

且沒給元素都與?S?中的某個元素同余。

然后計算?S?的積?∏S=1×2×3×…(p?1)=(p?1)!(modp)，

以及?S′?的積?∏S′=a×(a×2)×(a×3)×…(a×(p?1))=ap?1×(p?1)!(modp)。

因為?S?和?S′?都是模?p?意義下的完全剩余系，

所以兩集合的積同余，即?(p?1)!≡ap?1×(p?1)!(modp)。

最后化簡得?ap?1≡1(modp)。

證出費馬小定理，可以推出逆元式子：

1≡1(modp)a1×a?1≡ap?1(modp)a?1≡ap?2(modp)

對于冪的計算，可以使用快速冪。

時間復雜度?O(logA)。

此題還要用快讀

?由于 a/b 可能是超大整數（如 10^10000 量級），

需在讀入時直接對 19260817 取模，

避免高精度計算。

因此，

需要改造傳統的快讀為“即時取模”的快讀。
“即時取模”的快讀是一種在輸入大整數時直接進行取模運算的優化技術，

常用于處理需要大數運算但最終結果需取模的場景（如數論題目）。

其核心思想是在逐位讀取數字時同步計算模值，

避免存儲完整的大數。

“即時取模”的快讀代碼如下所示。

int read() {int x=0,f=1;char c=getchar();while(c<'0' || c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9') {x=(x*10LL+c-'0')%m;c=getchar();}return x*f;
}

代碼實現

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int m=19260817;int read() {int x=0,f=1;char c=getchar();while(c<'0' || c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0' && c<='9') {x=(x*10LL+c-'0')%m;c=getchar();}return x*f;
}
ll fast(ll a,ll n,ll p) {ll s=1;while(n) {if(n&1)s=s*a%p;n>>=1;a=a*a%p;}return s%p;
}
int main() {ll a=read(),b=read();if(b==0)cout<<"Angry!";else cout<<a*fast(b,m-2,m)%m;return 0;
}

各位大佬?

鼓勵一下

關注+收藏+點贊

好嗎