(A/B) mod C
問題描述
求(A/B)%C，但由于A和B實在太大了，我們只給出A % C，B % C。
(我們保證給定的A必能被B整除，且gcd(B,C) = 1)。
輸入描述
輸入一行三個整數，分別是A % C，B % C，C。
輸出描述
輸出(A/B)%C的值。
輸入示例1
22 11 49
輸出示例1
2
樣例解釋
(6000 / 60) % 49 = 2
60與49最大公約數為1，
6000%49 = 22，60 % 49 = 11
輸入22 11 49
輸出2
輸入示例2
1000 53 9973
輸出示例2
7922
輸入示例3
87 1022 9973
輸出示例3
6060
c++代碼(拓展歐幾里得算法 通用法,也就是C可以為任意實數)
#include<bits/stdc++.h>using namespace std;typedef long long ll;ll A, B, C;ll extend_gcd(ll a, ll b, ll &x, ll &y) {//返回d = gcd(a, b),并且找到ax + by = d的一個特解x,y。if (b == 0) { x = 1, y = 0; return a; }ll d = extend_gcd(b, a % b, y, x);y -= a / b * x;return d;
}ll mod_inverse(ll B, ll C) {//返回B mod C的逆ll x, y;extend_gcd(B, C, x, y);//x可能是負數return (x % C + C) % C;
}int main() {cin >> A >> B >> C;cout << (A * mod_inverse(B, C)) % C;return 0;
}//by wqs
c++代碼(特別地，當C為質數的時候，可以使用費馬小定理，不是通用法)
#include<bits/stdc++.h>using namespace std;typedef long long ll;ll A, B, C;ll fastPow(ll a, ll b, ll mod) {if (b == 0) return 1 % mod;if (b == 1) return a % mod;ll k = fastPow(a, b / 2, mod);if (b % 2 == 0) return (k * k) % mod;else return (((k * k) % mod) * a) % mod;
}ll mod_inverse(ll B, ll C) { return fastPow(B, C - 2, C); }int main() {cin >> A >> B >> C;//前提C為質數cout << (A * mod_inverse(B, C)) % C;return 0;
}//by wqs
題目解析
之所以要求gcd(B,C) = 1，是因為gcd(B,C) != 1的時候會有多個答案，這是硬性要求，否則題目無解。
然后我們要對C分類討論。
如果C是質數，一般使用費馬小定理。
如果C不是質數，一般使用通用法拓展歐幾里得算法。
一般涉及到除法取模，模值都是質數，費馬小定理用的更多。
