HDU1576 A/B

Time Limit: 1000MS

Memory Limit: 32768KB

64bit IO Format: %I64d & %I64u

Description

要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。

Input

数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

Output

对应每组数据输出(A/B)%9973。

Sample Input

2
1000 53
87 123456789 

Sample Output

7922
6060 

Source

HDU 2007-1 Programming Contest

本来好像是考扩展欧几里得的。

(A/B)%9973=K

(A/B)=K+9973x

A=K*B+9973*x*B

∵A%9973 = n， ∴KB%9973 = n, ∴kB = n + 9973t

列个同余方程求解。

然而也可以乘法逆元公式暴力解

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #define LL long long
 7 using namespace std;
 8 int n,b;
 9 int multi(int a,int k){
10     int now=a;
11     int res=1;
12     while(k){
13         if(k&1)res=(res*now)%9973+9973;
14         now=(now*now)%9973;
15         k>>=1;
16     }
17     return res;
18 }
19 int main(){
20     int T;
21     scanf("%d",&T);
22     while(T--){
23         scanf("%d%d",&n,&b);
24         int inv=multi(b%9973,9971); //乘法逆元 a^(p-2) %p=1
25         printf("%d
",n*inv%9973); 
26     }
27 }