codeforce Round On Sum of Fractions + stl 的应用

Let's assume that

v(n) is the largest prime number, that does not exceed n;
u(n) is the smallest prime number strictly greater than n.

Find $\text{[math]}$ .

Input

The first line contains integer t (1 ≤ t ≤ 500) — the number of testscases.

Each of the following t lines of the input contains integer n (2 ≤ n ≤ 109).

Output

Print t lines: the i-th of them must contain the answer to the i-th test as an irreducible fraction "p/q", where p, q are integers, q > 0.

Sample test(s)

input

2
2
3

output:1/6

7/30


1：欧几里得算法 计算GCD递归
gcd(a,b) == gcd(b,a%b);     a,b>0
2：判断素数:
3：符号重载

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string>
 4 #include<string.h>
 5 #include<map>
 6 #include<math.h>
 7 
 8 using namespace std;
 9 typedef long long LL;
10 bool Is_Prime(LL x)
11 {
12     for(LL i=2;i*i<=x;i++)
13         if(x%i == 0)
14             return 0;
15     return 1;
16 }
17 LL V_Down(LL x)
18 {
19     while(!Is_Prime(x))
20         x--;
21     return x;
22 }
23 LL U_Up(LL x)
24 {
25     x++;
26     while(!Is_Prime(x))
27         x++;
28     return x;
29 }
30 LL gcd(LL x, LL y)
31 {
32     return y==0?x:gcd(y, x%y);
33 }
34 class Node
35 {
36     public:
37         LL zi;
38         LL mu;
39     public:
40         Node(){};
41         Node(LL z ,LL m)
42         {
43             LL g=gcd(z,m);
44             zi=z/g;
45             mu=m/g;
46         };
47         Node operator +(const Node &A)const
48         {
49             LL m,z,g;
50             g=gcd(mu,A.mu);
51             m=mu/g*A.mu;
52             z=A.mu/g*zi+mu/g*A.zi;
53             g=gcd(z,m);
54             return Node(z/g,m/g);
55         }
56         Node operator - (const Node & A)const
57         {
58             LL m,z,g;
59             g=gcd(mu,A.mu);
60             m=mu/g*A.mu;
61             z=A.mu/g*zi-mu/g*A.zi;
62             g=gcd(z,m);
63             return Node(z/g,m/g);
64         }
65         Node &operator = (const Node &now)
66         {
67             this->mu=now.mu;
68             this->zi=now.zi;
69             return *this;
70         }
71 
72         friend ostream & operator <<(ostream &os,const Node &A)
73         {
74             os<<A.zi<<"/"<<A.mu;
75             return os;
76         }
77 
78 
79 };
80 int main()
81 {
82     int t;
83     LL x;
84     cin>>t;
85     while(t--)
86     {
87         cin>>x;
88         LL v=V_Down(x);
89         LL u=U_Up(x);
90         Node ans=Node(1,2)-Node(1,v);
91         Node sum=Node(x-v+1,u*v)+ans;
92         cout<<sum<<endl;
93     }
94     return 0 ;
95 }