2019杭电多校Contest5 1001 fraction

原题链接http://acm.hdu.edu.cn/showproblem.php?pid=6624

题意求一个最小正整数b，使得 a ≡ bx (mod p)

这里直接放上dls的题解，讲的贼清楚。

然后辗转相除一下，找到出口再把答案递归回去就ok了。

注意的是，b乘x会炸long long

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+5;
const ll mod=998244353;
void ggcd(ll au,ll ad,ll bu,ll bd,ll &b,ll &y)
{
    ll t=au/ad+1;
    if(t<=ll(bu/bd))
    {
        b=t,y=1;
        return ;
    }
    ggcd(bd,bu-bd*(t-1),ad,au-ad*(t-1),y,b);
    b+=(t-1)*y;
}
ll b,y,p,x;
ll mul(ll a,ll b)
{
    ll ans=0;
    while(b)
    {
        if(b&1)ans=(ans+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&p,&x);
        ggcd(p,x,p,x-1,b,y);
        ll a=mul(b,x);
        printf("%lld/%lld
",a,b);
    }
    return 0;
}