题目链接：Codeforces
396B On Sum of Fractions

题解来自：http://blog.csdn.net/keshuai19940722/article/details/20076297

题目大意：给出一个n，ans = ∑（2≤i≤n）1/(v(i)*u(i)), v(i)为不大于i的最大素数，u(i)为大于i的最小素数， 求ans，输出以分式形式。

解题思路：一開始看到这道题1e9，暴力是不可能了，没什么思路，后来在纸上列了几项，突然想到高中时候求等差数列时候用到的方法。详细叫什么不记得了。

1/(2*3) = (1/2  - 1/3) * 1/(3-2);

1/(3*5) = (1/3 - 1/5) * 1/(5-3);

然后值为1/(2*3)的个数有（3-2）个，为1/(3*5)的有（5-3）个。

这样如果有n，v = v(n),  u = u(n)；

1/(2*3) + 1/(3*5) * (5-3) + ...... + 1/(v*u) * (n-v+1)  (注意最后不是u-v个）

= 1/2 - 1/3 + 1/3 - 1/5 + ........ -1/v + 1/(v*u) *(n-v+1)

= 1/2 - 1/v + 1/(v*u)*(n-v+1)

p = u*v + 2*(n-v-u+1); q = 2*u*v;

记得约分，然后u和v就用枚举的方式。

int prmcnt;

bool is[N];int prm[M];

int getprm(int n)

{

    int i,j,k=0;

    int s,e=(int)(sqrt(0.0+n)+1);

    CL(is,1);

    prm[k++]=2;is[0]=is[1]=0;

    for(i=4;i<n;i+=2)is[i]=0;

    for(i=3;i<e;i+=2)

        if(is[i])

        {

            prm[k++]=i;

            for(s=i*2,j=i*i; j<n; j+=s)

                is[j]=0;

        }

    for(;i<n;i+=2)if(is[i])prm[k++]=i;

    return k;

}

bool judge(int x)

{

    if(x<MAXN-1)return is[x];

    for(int i=0;i<prmcnt;i++)

        if(x% prm[i] == 0)return 0;

    return 1;

}

AC代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <iostream>

#include <iomanip>

#include <cmath>

#include <map>

#include <set>

#include <queue>

using namespace std;

#define ls(rt) rt*2

#define rs(rt) rt*2+1

#define ll long long

#define ull unsigned long long

#define rep(i,s,e) for(int i=s;i<e;i++)

#define repe(i,s,e) for(int i=s;i<=e;i++)

#define CL(a,b) memset(a,b,sizeof(a))

#define IN(s) freopen(s,"r",stdin)

#define OUT(s) freopen(s,"w",stdout)

const ll ll_INF = ((ull)(-1))>>1;

const double EPS = 1e-8;

const int INF = 100000000;

const int MAXN = 1e5+5;

const int N = MAXN;

const int M=N;

int prmcnt;

bool is[N];int prm[M];

int getprm(int n)

{

    int i,j,k=0;

    int s,e=(int)(sqrt(0.0+n)+1);

    CL(is,1);

    prm[k++]=2;is[0]=is[1]=0;

    for(i=4;i<n;i+=2)is[i]=0;

    for(i=3;i<e;i+=2)

        if(is[i])

        {

            prm[k++]=i;

            for(s=i*2,j=i*i; j<n; j+=s)

                is[j]=0;

        }

    for(;i<n;i+=2)if(is[i])prm[k++]=i;

    return k;

}

bool judge(int x)

{

    if(x<MAXN-1)return is[x];

    for(int i=0;i<prmcnt;i++)

        if(x% prm[i] == 0)return 0;

    return 1;

}

int calv(int x)

{

    for(int i=x;i>1;i--)

        if(judge(i))return i;

    //

}

int calu(int x)

{

    for(int i=x+1;;i++)

        if(judge(i))return i;

}

ll gcd(ll x, ll y)

{

    return y == 0?

x:gcd(y,x%y);

}

int main()

{

    prmcnt=getprm(MAXN-1);

    int ncase,n;

    scanf("%d",&ncase);

    while(ncase--)

    {

        scanf("%d",&n);

        ll v= calv(n);

        ll u= calu(n);

        ll up =v*u-2*u-2*v+2*n+2;

        ll down=2*v*u;

        ll tmp=gcd(up,down);

        up/=tmp;

        down/=tmp;

        cout << up << '/' << down << endl;

    }

    return 0;

}