题目链接
题目概述
要求((A/B)\%9973)，但由于A很大，我们只给出(n(n=A\%9973))(我们给定的A必能被B整除，且(gcd(B,9973) = 1)).
数据的第一行是一个(T)，表示有(T)组数据。
每组数据有两个数(n(0 leq n < 9973))和(B(1 leq B leq 10^9)).对应每组数据输出((A/B)\%9973).
解题思路
利用逆元算除法取模的概念题,当然求逆元也可以用费马小定理来做.
扩展欧几里得
对于一个二元一次方程(ax+by=n, \, a,b,nin Z)当且仅当(gcd(a,b)=n)时方程有整数解.这个方程的解是先找到一个整数解((x_0,y_0)),然后通解:
把通解带入原来的方程得到:
所以只要求出一个特解原方程的通解就可以求出.
扩展欧几里得对应的代码如下,可以求得方程(ax+by=gcd(a,b))的一个特解((x_0+y_0)).
void extend_gcd(ll a, ll b, ll & x, ll & y) {
if( b == 0ll){
x = 1;
y = 0;
return;
}
extend_gcd(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - (a / b) * y;
}
逆元
如果(a pmod m = b pmod m),那么称(a,b)模(n)同余,记做(a equiv bpmod m).(ax equiv b pmod m)成为一元线性同余方程,即(ax-b)是(m)的整数倍,从而(ax-b=my),可以得到(ax+my=b),当(b=gcd(a,m))时可以用扩展欧几里得来解.可以使用逆元来解上面方程的任意情形,设(a')是(a pmod m)的逆元,即(aa'equiv1 pmod m).将上面的等式同时乘以(a'),得到(a'axequiv a'b pmod m),即(xequiv a'b pmod m).
对于方程(ax equiv1pmod m,)当(gcd(a,m)=1)时,相当于解方程(ax + my = 1.)用前面的扩展欧几里得就可求出一个特解.
ll mod_inverse(ll a, ll m){
ll x, y;
extend_gcd(a, m, x, y);
return ( m + x % m)% m;
}
利用费马小定理求逆元
若(p)为素数,(gcd(a,p) = 1),那么(a^{p-1} equiv 1pmod p).
另外一种形式:对于(ain Z, a^p equiv apmod p)
由上面的费马小定理可以推出方程(ax equiv 1pmod m,gcd(a,m)=1)的解(x = a^{m-1}).利用快速幂取模可以进行计算.
ll fast_exp_mod(ll a, ll b, ll p){
ll ans = 1;
while( b ){
if( b & 1){
ans = (ans * a) % p;
}
b >>= 1;
a = (a * a) % p;
}
return ans;
}
ll mod_inverse(ll a, ll m){
return fast_exp_mod(a, m - 2, m) % m;
}
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 9973;
ll fast_exp_mod(ll a, ll b, ll p){
ll ans = 1;
while( b ){
if( b & 1){
ans = (ans * a) % p;
}
b >>= 1;
a = (a * a) % p;
}
return ans;
}
void extend_gcd(ll a, ll b, ll & x, ll & y) {
if( b == 0ll){
x = 1;
y = 0;
return;
}
extend_gcd(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - (a / b) * y;
}
ll mod_inverse(ll a, ll m){
// ll x, y;
// extend_gcd(a, m, x, y);
// return ( m + x % m)% m;
return fast_exp_mod(a, m - 2, m) % m;
}
int main(int argc, const char** argv) {
int T;
scanf("%d", &T);
for (int i = 0; i < T; ++i){
int n, b;
scanf("%d%d", &n, &b);
ll ans = mod_inverse(b, M);
ans = (ans * n) % M;
printf("%lld
", ans);
}
return 0;
}