【HDU1576】A/B 求逆元 – TK-Xiong`s Blog

逆元：
对于正整数a和b，如果有a*x ≡ 1(mod n),那么把同余方程中x的最小正整数解叫做a模b的逆元.
拓展欧几里得：
扩展欧几里德算法是用来在已知a,b求解一组x，y，使它们满足贝祖等式： ax+by=gcd(a,b)=d（解一定存在，根据数论中的相关定理）。

当a和b互素时，a模b有的乘法逆元有唯一解。如果不互素，则无解。
因此我们可以知道当gcd(a,b)==1时，x为a模b的逆元，y为b模a的逆元.

题目：
A/B

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

解法：
//当我们要求 (a/b)mod p 的值，且a很大，无法直接求得a/b的值时，我们就要用到乘法逆元。
//我们可以通过求b关于p的乘法逆元k，将a乘上k再模p，即(a*k)mod p。其结果与(a/b)mod p等价。

#include <iostream>
using namespace std;

const int MOD = 9973;

long long extend_gcd(long long a, long long b, long long &x , long long &y)
{
	if(a==0&&b==0) return -1;
	if(b==0){ x = 1;y = 0;return a; }
	else{
	    long long d=extend_gcd(b,a%b,y,x);
	    y-=a/b*x;
	    return d;
	}
}

long long mod_reverse(long long a,long long n)
{
    long long x,y;
    long long d=extend_gcd(a,n,x,y);
    if(d==1) return (x%n+n)%n;
    else return -1;
}

int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		int n , B;
		cin >> n >> B;
		int x = mod_reverse(B,MOD);
        cout << n*x%MOD << endl;
	}
}

#include <iostream>

using namespace std;

const int MOD = 9973;

long long extend_gcd(long long a, long long b, long long &x , long long &y)

{

if(a==0&&b==0) return -1;

if(b==0){ x = 1;y = 0;return a; }

else{

long long d=extend_gcd(b,a%b,y,x);

y-=a/b*x;

return d;

}

long long mod_reverse(long long a,long long n)

{

long long x,y;

long long d=extend_gcd(a,n,x,y);

if(d==1) return (x%n+n)%n;

else return -1;

}

int main()

{

int T;

cin >> T;

while(T--)

{

int n , B;

cin >> n >> B;

int x = mod_reverse(B,MOD);

cout << n*x%MOD << endl;

}

来自bin神的模板…

拓展欧几里得算法计算逆元…

【HDU1576】A/B 求逆元

Tagged on: Algorithm Math