Java没有传引用这种东西,long的包装类又是final的,所以只能用数组来代替一下
拓展欧几里德这东西真实难懂,逆元这东西也是难懂
import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
static long n,b;
static final int MOD=9973;
static long exgcd(long a,long b,long[] x,long[] y){
if(b==0){
x[0]= 1L;
y[0]= 0L;
return a;
}
long d=exgcd(b,a%b,x,y);
long tmp=x[0];
x[0]=y[0];
y[0]=tmp-a/b*y[0];
return d;
}
static long inv(long a,long m){
long[] x={
0};
long[] y={
0};
long d=exgcd(a,m,x,y);
if(d==1){
return (x[0]%m+m)%m;
}
return -1;
}
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
int t=cin.nextInt();
while(t-->0){
n=cin.nextLong();
b=cin.nextLong();
long c=inv(b,MOD);
System.out.println(n*c%MOD);
}
}
}