Problem 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
21000 5387 123456789
Sample Output
79226060
#include <cstdio>#include <iostream>using namespace std;int main(){int t;cin >> t;while(t –){long long int n,b;int i;cin >> n >> b;for(i = 1;i <= 9973;i++){if(i * b % 9973 == 1){break;}}cout << n * i % 9973 << endl;}return 0;} a/b % n = a * b^-1 %n,也就是a/b可以换成a乘上b对于模n群的逆元的模
版权声明:本文为博主原创文章,未经博主允许不得转载。
与那些新人和旧人们共同经历吧!