A/B HDU - 1576 (逆元或拓展欧几里得或数学公式)多解法求大数结果

 

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

思维:(1)逆元+扩展欧几里得算法:满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元。当且仅当gcd(k,p) = 1,如果可逆则可定义除法 x/k = x * a mod p

(2)扩展欧几里得算法+递推公式:运用扩展欧几里德算法能解出gcd(a,b)=a*x1+b*y1的x1和y1的值。

(3)数学思维解法:推等式+枚举某数让等式成立。

题目:

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

AC代码

逆元:为什么要有乘法逆元呢? 当我们要求(a/b) mod p的值,且a很大,无法直接求得a/b的值时,我们就要用到乘法逆元。 我们可以通过求b关于p的乘法逆元k,将a乘上k再模p,即(a*k) mod p。其结果与(a/b) mod p等价。 (A/B)%9973,但由于A很大且gcd(B,9973) = 1),所以我们可以求B的逆元然后 k*B = 1 mod n 然后改写式子 (A/B)%9973 = A % 9973 * k%9973 B的逆元就用扩展欧几里德解  k*B = 1 mod n --> k*B + m*n = 1;

#include<iostream>/**逆元+拓展欧几里得*/
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long int64;
int64 Exgcd(int64 a,int64 b,int64 &x,int64 &y)
{
    if(b == 0)
    {
        x = 1,y = 0;
        return a;
    }
    else
    {
        int64 r = Exgcd(b,a%b,x,y);
        int64 temp = x;
        x = y, y = temp - a/b*y;
        return r;
    }
}
int main()
{
    int t;
    int64 n,b = 9973,B,x,y;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64d%I64d",&n,&B);
        int64 d = Exgcd(B,b,x,y);
        b = b / d;
        x = x / d ;
        x = (x % b + b) % b;/*求a最小正整数逆元x=x0+(a/gcd)*t*/
        printf("%I64d\n",(n%9973 * x%9973)%9973);/*x为n的逆元*/
    }
    return 0;
}

拓展欧几里得:

根据题目我们知道: n=A%9973,则n=A-A/9973*9973。又A/B=x,则A=Bx。所以Bx-A/9973*9973=n。即Bx-9973y=n。 在这里我们知道只要求出x的值就能算出x%9973的值,也就是(A/B)%9973的值。 利用扩展欧几里德算法可求出gcd(B,9973)=Bx1+9973y1=1的x1。题中说gcd(B,9973)=1;所以等式两边 同乘以n,得B(n*x1)-9973(-n*y1)=n。可知n*x1就是B*x-9973*y=n的解了!!!即x=n*x1。 在扩展欧几里得算法中得到的x可能为负值,所以还需要x=(x%9973+9973)%9973。

#include<cstdio>/**推等式+拓展欧几里得*/
#include<cstring>
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,n,b,x,y;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&b);
		extgcd(b,9973,x,y);
		x*=n;
		x=(x%9973+9973)%9973;
		printf("%d\n",x);
	}
	return 0;
} 

数学思维解法: 思路:设X=(A/B)%9973        因为n=A%9973,所以A=k*9973+n (k为一常数)        又因为X=(A/B)%9973,所以A/B=d*9973+X (d为一常数)      两边同乘以B,得:A=B*d*9973+B*X 即B*d*9973+B*X=k*9973+n 移项得:   B*d*9973+B*X-n=k*9973 所以题意转为  只要满足(B*X-n)%9973=0,X即为要求的结果。n的值知道,B的值知道,又因为x的取 值范围是0到9972,因此枚举x的值即可,满足条件的就是答案。

#include<cstdio>/**推等式+枚举某数让等式成立*/
int main()
{
	int n,a,i,t;
	long long b;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%lld",&n,&b);
		for(i=0;i<9973;++i)
		{
			if((b*i-n)%9973==0)
				break;
		}
		printf("%d\n",i);
	}
	return 0;
}

 

上一篇:ocaml快餐教程(3) - 基本结构


下一篇:go 将数组按指定大小分隔