code chef：Cool Guys题解

code chef：Cool Guys题解2015-02-25

All submissions for this problem are available.

Given an integer N. Integers A and B are chosen randomly in the range [1..N]. Calculate the probability that the Greatest Common Divisor（GCD） of A and B equals to B.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case consists of a single integer N on a separate line.

Output

For each test case, output a single line containing probability as an irreducible fraction.

Given an integer N. Integers A and B are chosen randomly in the range [1..N]. Calculate the probability that the Greatest Common Divisor（GCD） of A and B equals to B.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case consists of a single integer N on a separate line.

Output

For each test case, output a single line containing probability as an irreducible fraction.

Example

Input:3123Output:1/13/45/9

Constraints

1<=T<=10³

1<=N<=10⁹

本题也是个数学题。

有两个知识点：

1 求最大公约数的算法

2 求小于等于一个数值的两数相乘的对数 - 这个又是数学公式

据说这里是数学详细解析，感兴趣的研究一下：

http://matwbn.icm.edu.pl/ksiazki/mon/mon42/mon4204.pdf

OJ系统：

http://www.codechef.com/problems/COOLGUYS/

long long mGcd（long long a, long long b）{long long c = 0;while （b）{c = b;b = a % b;a = c;}return c;}long long pairsOfCoolguys（long long n）{long long ans = 0;long long sq = （long long）sqrt（n）;for （unsigned i = 1; i <= sq; i++）{ans += n/i;}ans = （ans<<1） - sq*sq;return ans;}void coolguys（）{long long n = 0;int T = 0;cin>>T;while （T--）{cin>>n;long long ps = pairsOfCoolguys（n）;n *= n;long long d = mGcd（ps, n）;cout <<（ps/d） << "/"<<（n/d）<<"
";}}

From：csdn博客靖心