A/B （真·数论水题）（乘法逆元）A/B

60 阅读 0 评论 40 点赞

我是靠谱客的博主动听秋天，最近开发中收集的这篇文章主要介绍A/B （真·数论水题）（乘法逆元）A/B，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A/B

要求(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

第一种乘法逆元拓展欧几里得
首先我们应该很清楚的知道(A/B)%9973 !=(A%9973) /( B % 9973)的。。也就是说除法是不满足同余定理的。那么我们怎么计算类似除法的同余定理的呢？？
下面我们了解一下乘法逆元

下面就是乘法逆元的概念：

若ax≡1 mod f, 则称a关于模f的乘法逆元为x。

一个数有逆元的充分必要条件是gcd(a,f)=1，此时逆元唯一存在
逆元的含义：模f意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

那么这个问题为什么能够用乘法逆元来求解呢？？

(A / B) % 9973 = (A * B’) % 9973
B’为B关于9973的乘法逆元。。化成乘法来进行求解就好了。。

为什么可以这样呢？
因为 B*B’ % 9973 = 1
所以(A * 1 / B) % 9973 = (A * B * B’ / B ) % 9973 =(A * B’) % 9973 是合法的。。。

这样一想就很简单了。。

逆元求解一般利用扩欧。
扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。

对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然
存在整数对 x，y ，使得 gcd（a，b）=ax+by。

在本题中f=9973且已知gcd(B,f)=1
重点是求B的逆元，设B的逆元为x
Bx≡1%f
所以Bx+f*y=1=gcd(B,f)
在扩展欧几里得算法中得到的x可能为负值，所以还需要x=(x%9973+9973)%9973。

#include<cstdio>
using namespace std;
const int f=9973;
void extgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return ;
	}
	else{
		extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,b,x,y;
		scanf("%d%d",&n,&b);
		extgcd(b,f,x,y);
		x=(x%f+f)%f;
		int ans=((n%f)*(x%f))%f;
		printf("%dn",ans);		
	}
	return 0;
}

第二种数学暴力推
由n=A%9973,可得A=k9973+n
设A/B=C，则（A/B）%9973=C%9973=X(所要求的结果），
所以C=p9973+X，即A/B=p9973+X
所以A=Bp9973+BX
因为A=k9973+n
所以k9973+n=Bp9973+BX
所以BX-n=(k-B*p)9973
所以（BX-n）%9973=0

已知B和n,又知0<=X<9973,所以枚举X值即可，满足条件即是答案

#include<cstdio>
using namespace std;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,b;
		scanf("%d%d",&n,&b);
		for(int i=0;i<9973;i++){
			if((((b%9973)*i)%9973-n)%9973==0){//运用模运算性质防止超int 
				printf("%dn",i);
				break;
			}
		}
	}
	return 0;
}