扩展欧几里得--hdu1576

Problem Description

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

Input

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

Output

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

Sample Input

2
1000 53
87 123456789

Sample Output

7922
6060

扩展欧几里得模板

由题意得

[ans=(frac{A}{B})\%9973\ n=A\%9973 \ 得ans*B+9973*x = A = n+9973*y \ frac{ans}{n} *B+9973*(x*B-y) = n \ 因gcd(B, 9973) = 1 \ 即形如ax+by = gcd(a, b) ]

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>

using namespace std;
typedef long long LL;
typedef pair<double, double> PDD;
typedef pair<LL, LL> PLL;

const LL N = 1e6+50;
const LL MOD = 1e9+7;
const LL INF = 0x3f3f3f3f;

#define lson l, m, rt>>1
#define rson m+1, r, rt>>1|1

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b)
    {
        x = 1;y = 0;
        return a;
    }
    LL ret = exgcd(b, a%b, y, x);
    y -= x*(a/b);
    return ret;
}

int main()
{
    int T;cin >> T;
    while(T--)
    {
        LL n, B;cin >> n >> B;
        LL x, y;
        exgcd(B, 9973, x, y);
        cout << ((x*n)%9973+9973)%9973 << endl;//x可能为负数
    }
    return 0;
}

扩展欧几里得--hdu1576

扩展欧几里得模板

相关推荐