HDU1576 A/B

文章目录

1. 1. 题意
2. 2. 分析

原题

题意

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

分析

打完CF又瞅了一眼这个题，完全不能理解我那天为何推了半个小时。。。真心是随便2分钟就推出来的公式，大概当时是个傻逼，或者我看完kalafina的演唱会之后，可爱的kaiko让我智商上升了！！（表白kalafina真心是三只都好棒啊！

（k*9973+n）/ B = q*9973+r
 9973^q*B+r*B = 9973*k+n
 9973*(q*B-k)+r*B = n

求r，裸的不行的扩展欧几里得二元一次不定方程。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
void exgcd(ll a,ll b,ll& x,ll& y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-a/b*y;
    return;
}
int main(){

    ll n,b,t,x,y;
    while(scanf("%I64d",&t)!=EOF){
        while(t--){
            scanf("%I64d%I64d",&n,&b);
            exgcd(b,9973,x,y);
            x=((n*x)%9973+9973)%9973;
            if(x<0){
                x+=9973;
            }
            printf("%I64d\n",x);
        }
    }
}