Codeforces 396B On Sum of Fractions(数论）

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

题目大意：给出一个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就用枚举的方式。

#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;
const int N = 1e5+10;
typedef long long ll;

int cnt, prime[N], flag[N];

void init () {
	cnt = 0;
	memset(flag, 0, sizeof(flag));

	for (int i = 2; i < N; i++) if (!flag[i]) {
		prime[cnt++] = i;
		for (int j = i*2; j < N; j += i) flag[j] = 1;
	}
}

bool isPrime (int k) {
	if (k < N) return !flag[k];

	for (int i = 0; i < cnt && prime[i] <= k; i++)
		if (k%prime[i] == 0) return false;
	return true;
}

ll under (int n) {
	for (int i = n; i >= 2; i--)
		if (isPrime(i)) return i;
	return 0;
}

ll up (int n) {
	for (int i = n + 1; i; i++)
		if (isPrime(i)) return i;
	return 0;
}

int gcd(ll p, ll q) {
	if (!q) return p;
	else return gcd(q, p%q);
}

int main () {
	init();

	int cas, n;
	scanf("%d", &cas);

	while (cas--) {
		scanf("%d", &n);
		ll v = under(n);
		ll u = up(n);

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

		ll d = gcd(p, q);
		cout << p/d << "/" << q/d << endl;
	}
	return 0;
}