hdu6624 fraction 辗转相除法

题意：给定p和x，求最小的b，使 a≡bx(mod p)。

思路：先把式子进行转化：

　　　　a≡bx(mod p)

　　　　a=bx - pc

　　　　∵ 0 < a < b

　　　　∴ 0 < bx - pc < b

　　　　即 $frac{p}{x}$ $leq$ $frac{b}{a}$ < $frac{p}{x-1}$

　　　这样就转化为：求满足值在所给的两分数之间时，最小的分子分母是多少（可以用辗转相除法求解）。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 // 满足 a/b <= x/y < c/d 的最小的x和y 
 5 void solve(ll a,ll b,ll c,ll d,ll &x,ll &y){
 6     ll z=(a+b-1)/b;
 7     if(z<=c/d){
 8         x=z,y=1;
 9         return;
10     }
11     a-=b*(z-1),c-=d*(z-1);
12     solve(d,c,b,a,y,x);
13     x+=y*(z-1);
14 }
15 int main()
16 {
17     ll p,x;
18     int T;
19     scanf("%d",&T);
20     while(T--){
21         scanf("%lld%lld",&p,&x);
22         ll a,b,c;
23         solve(p,x,p,x-1,b,c);
24         a=b*x-p*c;
25         printf("%lld/%lld
",a,b);
26     }
27     return 0;    
28 }