HDU 1576 A/B(扩展欧几里德变形)

一道扩展欧几里德的变形题目

题中给出 n = A%9973 → n = A - A/9973*9973(若x = A%B 则 x = A - A/B*B)

因为A能整除B 所以设x = A/B → A = B*x 

所以原式 = B*x - A/9973*9973 = n 设y = A/9973

B*x - 9973y = n

然后利用扩展欧几里德求出x即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
int n, B, T;
int gcd(int  a, int b){  
     if(b == 0) return a;
     return gcd(b, a%b);
}
void exgcd( int a, int b, int &x, int &y ){
    if( b== 0 ){
        x= 1;
        y= 0;
        return;
    }
    exgcd( b, a% b, x, y );
    int t = x;
    x = y;
    y= t- a/ b* y;
    return;
}
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &B);
        int a = B;
        int b = 9973;
        int m = n;
        int d = gcd(a,b);
        int a1, b1, m1,x ,y;
        a1 = a/d; b1 = b/d; m1 = m/d; 
        exgcd(a1, b1, x, y);
        int x1 = x*m1;
        int ans = x1%b1;
        while(ans < 0){
            ans += b1;
        }
        printf("%d
", ans%9973);
        
    }
    return 0;
}