HDU 2669 Romantic(扩展欧几里得)

题目链接

解题思路

  扩展欧几里得的模板题,题目求x最小的正整数解,但是我们用exgcd求出来的是一组特解.怎么办呢?其实很简单,只要在等式左边加上k个(a imes b),然后再减去k个(a imes b)即可,稍微变形一下就是x加上k个b然后y再减去k个a.

代码

ll x, y;      
void exgcd(ll a, ll b) {
    if (!b) {
        x = 1; y = 0;
        return;
    }
    exgcd(b, a%b);
    ll t = x; x = y;
    y = t-a/b*y;
}
int main(){
    int t; cin >> t;
    while(t--) {
        ll n, b;
        cin >> n >> b;
        exgcd(b, 9973);
        x = (x%9973+9973)%9973;
        cout << n*x%9973 << endl;
    }
    return 0;
}