fraction
原题：https://acm.hdu.edu.cn/showproblem.php?pid=6624
Problem Description
Many problems require printing the probability of something. Moreover, it is common that if the answer is ab, you should output a×b−1(modp) (p is a prime number). In these problems, you cannot know the exact value of the probability. It's so confusing!!! Now, we want to reverse engineer the exact probability from such calculated output value x. We do so by guessing the probability is the one with the minimum b such that a×b−1=x(modp). Now we invite you to solve this problem with us!
You are given two positive integers p and x, where p is a prime number.
Please find the smallest positive integer b such that there exist some positive integer a satisfying a<b and a≡bx(modp).
Input
The first line contains an integer T indicating there are T tests. Each test consists of a single line containing two integers: p,x.
* 1≤T≤2×105
* 3≤p≤1015
* p is a prime
* 1<x<p
Output
For each test, output a line containing a string represents the fraction ab using the format "a/b" (without quotes).
Sample Input
3
11 7
998244353 554580197
998244353 998244352
Sample Output
2/5
8/9
499122176/499122177
题目大意：
给出正整数x与p，找到最小的b，使得存在正整数a<b，并且满足：a=bx(mod p)
个人解法：
它和同余没有任何关系……
根据题解，大概做这么一件事：
令a=bx+py，由题意0<a=bx+py<b，可以得出y<0，并且：
然后题解表示：
于是去找Code Jam的题解，但是没人写。
于是就只好翻墙去找。看了半天，又转到wiki。终于在wiki找到了这一性质：
大意是：
区间(a,b)的 最佳分数 是指：某一个分数c/v，满足a<c/v<b，并且c和v最小（c和v都是整数）。也就是我们要求的答案。
把下界分数a和上界分数b转化为连分数数列A1,A2,B1,B2。
（注意有理数的连分数表现形式有两种，一种是最后一个数字x不是1的，另一种是把第一种的最后一个数字x拆分为x-1和1的）
（什么是连分数可以参考一篇百度文库的文章）。
对于(A1,B1)(A2,B1)(A1,B2)(A2,B2)四组数列的每一组，找到两个数列第一个不相同的位置p，我们的 最佳分数 的连分数表示形式C 可能是如下数列：
C[1..p-1]位都是相同的，等于A[1..p-1]或B[1..p-1]。
C[p]=min(A[p],B[p])。如果A[p]或者B[p]不存在，则视为正无穷。
把一个分数转换为连分数是O(logn)的。可以使用辗转相除法。因此这是一个“经典问题”。
之前写了一次，常数有点大，改了一下。跑了951ms……