题解与代码 - On Sum of Fractions

## 数学推导

$$
\begin{aligned}
   & \sum\limits_{i=2}^{n}\dfrac 1{u(i)v(i)} \\
=\ & \dfrac 1{2\times 3}+\dfrac 1{3\times 5}+\dfrac 1{3\times 5}+\dfrac 1{5\times 7}+\dfrac 1{5\times 7}+\cdots+\dfrac 1{u(n)v(n)} \\
=\ & \dfrac{3-2}{2\times 3}+\dfrac{5-3}{3\times 5}+\dfrac{7-5}{5\times 7}+\cdots+\dfrac{u(n)-u(u(n)-1)}{u(u(n)-1)u(n)}+\dfrac{n-u(n)+1}{u(n)v(n)} \\
=\ & \left(\dfrac 12-\dfrac 13\right)+\left(\dfrac 13-\dfrac 15\right)+\left(\dfrac 15-\dfrac 17\right)+\cdots+\left(\dfrac 1{u(u(n)-1)}-\dfrac 1{u(n)}\right)+\dfrac{n-u(n)+1}{u(n)v(n)} \\
=\ & \dfrac 12-\dfrac 1{u(n)}+\dfrac{n-u(n)+1}{u(n)v(n)} \\
=\ & \dfrac 12+\dfrac{n-u(n)-v(n)+1}{u(n)v(n)}.
\end{aligned}
$$

那么只需要暴力求出 $u(n)$ 和 $v(n)$ 即可就算出答案。

```cpp
// 2022.06.30

#include<bits/stdc++.h>
using namespace std;

int T,n;

inline bool prime(int x){
    if(x<2)return false;
    int t=sqrt(x);
    for(int i=2;i<=t;i++)
        if(x%i==0)return false;
    return true;
}

long long Gcd(long long x,long long y){
    if(y==0)return x;
    return Gcd(y,x%y);
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int u=n+1,v=n;
        while(!prime(u))u++;
        while(!prime(v))v--;
        long long ans1=n-u-v+1,ans2=(long long)u*v;
        ans1*=2,ans2<<=1,ans1=ans2/2+ans1;
        long long gcd=Gcd(ans1,ans2);
        printf("%lld/%lld\n",ans1/gcd,ans2/gcd);
    }
    return 0;
}

```

On Sum of Fractions

数学推导

$\begin{aligned} & \sum\limits_{i=2}^{n}\dfrac 1{u(i)v(i)} \\ =\ & \dfrac 1{2\times 3}+\dfrac 1{3\times 5}+\dfrac 1{3\times 5}+\dfrac 1{5\times 7}+\dfrac 1{5\times 7}+\cdots+\dfrac 1{u(n)v(n)} \\ =\ & \dfrac{3-2}{2\times 3}+\dfrac{5-3}{3\times 5}+\dfrac{7-5}{5\times 7}+\cdots+\dfrac{u(n)-u(u(n)-1)}{u(u(n)-1)u(n)}+\dfrac{n-u(n)+1}{u(n)v(n)} \\ =\ & \left(\dfrac 12-\dfrac 13\right)+\left(\dfrac 13-\dfrac 15\right)+\left(\dfrac 15-\dfrac 17\right)+\cdots+\left(\dfrac 1{u(u(n)-1)}-\dfrac 1{u(n)}\right)+\dfrac{n-u(n)+1}{u(n)v(n)} \\ =\ & \dfrac 12-\dfrac 1{u(n)}+\dfrac{n-u(n)+1}{u(n)v(n)} \\ =\ & \dfrac 12+\dfrac{n-u(n)-v(n)+1}{u(n)v(n)}. \end{aligned}$

那么只需要暴力求出 $u(n)$ 和 $v(n)$ 即可就算出答案。

代码

// 2022.06.30

#include<bits/stdc++.h>
using namespace std;

int T,n;

inline bool prime(int x){
    if(x<2)return false;
    int t=sqrt(x);
    for(int i=2;i<=t;i++)
        if(x%i==0)return false;
    return true;
}

long long Gcd(long long x,long long y){
    if(y==0)return x;
    return Gcd(y,x%y);
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int u=n+1,v=n;
        while(!prime(u))u++;
        while(!prime(v))v--;
        long long ans1=n-u-v+1,ans2=(long long)u*v;
        ans1*=2,ans2<<=1,ans1=ans2/2+ans1;
        long long gcd=Gcd(ans1,ans2);
        printf("%lld/%lld\n",ans1/gcd,ans2/gcd);
    }
    return 0;
}