A/B//HDOJ-1576//数论

A/B//HDOJ-1576//数论

题目

要求(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
链接:https://vjudge.net/contest/351853#problem/C

思路

A=9973k+n,A/B=k19973+ans
联立，9973k=Bk19973+Bans-n
因此(B*ans-n)%9973=0

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 0x3fffffffusing namespace std;int main(){
    long long b,n,x,t;cin>>t;while(t--){
    cin>>n>>b;for(int i=1;i<9973;i++){
    if((((b%9973)*i)%9973-n)%9973==0){
    cout<<i<<endl;break;}}}return 0;
}

注意

(a+b) % c==(a % c + b % c) %c
(a-b) % c==(a % c - b % c) % c
(a*b) % c==(a % c * b % c) % c