HDU多校第五场 1001 fraction —— 辗转相除求分数中间值

题目链接：点我啊╭(╯^╰)╮

题目大意：

    分数取模为 $a/b=x$   $(mod$  $p)$
    现给出 $x$ 与 $p$
    求最小的分数解 $a/b$

解题思路：

辗转相除求中间值:

$$p=11,x=7$$
$$\frac{11}{7}<\frac{x}{y}<\frac{11}{6}$$
化真分数 $=>$ $$\frac{4}{7}<\frac{x?y}{y}<\frac{5}{6}$$
取倒数 $=>$ $$\frac{6}{5}<\frac{y}{x?y}<\frac{7}{4}$$

化真分数 $=>$ $$\frac{1}{5}<\frac{2y?x}{x?y}<\frac{3}{4}$$
取倒数 $=>$ $$\frac{4}{3}<\frac{x?y}{2y?x}<\frac{5}{1}$$

发现 $(\frac{4}{3},\frac{5}{1})$ 内有最小整数 $2$
最后回溯得到答案

核心：辗转相除求分数中间值

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <int,int>;void gao(ll pa, ll pb, ll qa, ll qb, ll &x, ll &y){ll z = pa / pb;	//	取向下整除的部分 if(z + 1 <= qa / qb){x = z + 1, y = 1;return;}pa -= z * pb;	//	取真分数 qa -= z * qb;gao(qb, qa, pb, pa, y, x);	//	取倒数 x += z * y;
}ll p, a, x, y;
int main() {int T;scanf("%d", &T);while(T--){scanf("%lld%lld", &p, &a);gao(p, a, p, a-1, x, y);a = x * a - p * y;printf("%lld/%lld\n", a, x);}
}