###name
Meteor
###descirption
hough time passes, there is always someone we will never forget.
“The probability of being hit by a meteor is one in a billion, but it is much more miraculous, to meet you in my life.” said Tom to Jerry with affection.
“One in a billion? I may not agree with you.” answered Jerry proudly, “Let’s do the math.”
…
Thinking of the days they have happily spent together, Tom can’t help bursting into tears. Though Jerry has been gone for a long time, Tom still misses him every day. He remembers it was a sunny afternoon when Jerry and him were lying in the yard, working on the probability of a man being hit by a meteor.
Unlike Jerry, he was always slow. Jerry got the answer soon, but Tom was stuck as usual. In the end, Tom lost patience and asked Jerry to tell him the answer.
“I can’t be so straightforward,” snickered Jerry, “the only thing I will tell you is that the answer is $\frac{p}{q}$, where p,q≤n,gcd(p,q)=1.”
“Is it $\frac{1}{n}$?”
“Is it $\frac{1}{n-1}$?”
…
If answered “No” , he would try the minimum larger number that satisfies the requirement.
Tom only remembered n given by Jerry, and k, the times that he tried, but forgot what matters the most: Jerry’s answer. Now, he wants you to help him find it.
###input
The first line contains an integer $T(T≤10^2)$, the number of test cases.
The next T lines, each line contains two number$s, n,k(2≤n≤10^6)$, indicating a query.
The answer is guaranteed to be in (0,1].
###output
T lines, each line contains a fraction in term of p/q ,where gcd(p,q)=1.
###sample input
5
4 6
5 1
9 9
3 4
7 11
###sample output
1/1
1/5
1/3
1/1
3/5
###toturial
$$
\begin{aligned}
&答案肯定是找到一个分子分母小于n的分数\frac{p}{q}他满足下面的特征\
&(\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=1][\frac{i}{j} \leq \frac{p}{q}]) = k\
&我们对左式化简\
&=\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=1][i \leq \frac{p}{q}j]\
&=\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^n[gcd(i,j)=1]\
&=\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^ne(gcd(i,j))\
&=\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^n(u*1)(gcd(i,j))\
&=\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^n\sum_{d|gcd(i,j)}u(d)*1(d)\
&=\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^n\sum_{d|gcd(i,j)}u(d)\
&=\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^n\sum_{d|i,d|j}u(d)\
&=\sum_{d=1}^{n}u(d)\sum_{i=1}^{\lfloor \frac{p}{q}j\rfloor}\sum_{j=1}^n[d|i,d|j]\
&=\sum_{d=1}^{n}u(d)\sum_{xd=1}^{\lfloor \frac{p}{q}(yd)\rfloor}\sum_{yd=1}^n[d|(xd),d|(yd)]\
&=\sum_{d=1}^{n}u(d)\sum_{x=1}^{\lfloor\frac{\lfloor \frac{p}{q}(yd)\rfloor}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{n}{d}\rfloor}1\
&=\sum_{d=1}^{n}u(d)\sum_{y=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{\lfloor \frac{p}{q}(yd)\rfloor}{d}\rfloor\
&=\sum_{d=1}^{n}u(d)\sum_{y=1}^{\lfloor\frac{n}{d}\rfloor}{\lfloor \frac{p}{q}y\rfloor}\
\end{aligned}
$$
这里是可以求出答案的,对d分块，右边的部分采用类欧几里得算法
我们一直往下二分，直到区间足够小，最后用 Stern-Brocot Tree 或 法雷序列找出答案
###code
1 |
|
