首页 > 代码库 > HDU 1576 A/B(扩展欧几里德变形)

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

2024-07-14 12:43:38   222人阅读

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

题中给出 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\n", ans%9973);            }    return 0;}

 


联系
我们