1576. A/B

2020-05-30

HDOJ

逆元

3 分钟读完 (大约 385 个字) 0次访问

HDOJ 1576. A/B

题目：1576. A/B

问题描述：

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

输入：

数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

输出：

对应每组数据输出(A/B)%9973。

样本输入：

2
1000 53
87 123456789

样本输出：

7922
6060

方法：扩展欧几里得

思路：令m = 9973，inv(a)表示a关于m的逆元，根据题意可得 (A / B) % m = ((n + k * m) * inv(B)) % m = ((n + k * m) % m) * (inv(B) % m) = (n % MOD) * (inv(B) % MOD) = n * inv(B) % m。所以只需求n * inv(B) % m的值即可。本题使用扩展欧几里得求逆元。

运行数据：执行用时：249MS，内存消耗：9316K

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		long m= 9973;
		
		while (T-- > 0) {
			long n = sc.nextLong();
			long B = sc.nextLong();
			
			long result = n * inv(B) % m;
			System.out.println(result);
		}
	}
	
	private static long x,y;
	
	// 拓展欧几里得算法
	private static void exgcd(long a, long b) {
		if (b == 0) {
			x = 1;
			y = 0;
			return ;
		}
		
		exgcd(b, a % b);
		long k = x;
		x = y;
		y = k - a / b * y;
		
	}
	
	// 求逆元
	private static long inv(long a) {
		long b = 9973;
		exgcd(a, b);
		return (x + b) % b;
	}
}