首页 > 其他 > 详细

1576 mod 运算的逆元

时间:2015-07-18 18:36:01      阅读:225      评论:0      收藏:0      [点我收藏+]
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
2 1000 53 87 123456789
 

Sample Output
7922 6060


#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群的逆元的模

版权声明:本文为博主原创文章,未经博主允许不得转载。

1576 mod 运算的逆元

原文:http://blog.csdn.net/qq_24667639/article/details/46944291

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!