Codeforces 396(#232 Div1) B. On Sum of Fractions

問題

u(n) = n以下の最大の素数
v(n) = nより大きな最小の素数
とするとき、与えられたnに対して
Σ[i = 2 to n] 1 / u(i)v(i)を既約分数の形で求めよ。

制約条件

1テストにつき500個のnが与えられる。
n≦10^9

方針

(b - a) / ab + (c - b) / bc = (c - a) / acになるので、
c - bはちょうど次の素数までの間隔になっていて全部打ち消しあってハッピー。

n+1以下の最大の素数をpとすれば、
pの部分までのΣが(p - 2) / 2*pになって、
そこから先が(n+1 - p) / p*qになるので足し算して約分するだけ。

だけやん。気づけよ。最悪愚直に試せよ。頭悪すぎる……
制約からO(1)とかそれくらいで出来て、しかも多倍長が多分いらなそうだし、n以下の最大の素数の簡単な式とかで書けるに決まってるんだよなあ。

ソースコード

inline bool isprime(int n){
	if(n % 2 == 0) return 0;
	for(int i = 3; i * i <= n; i += 2) if(n % i == 0) return 0;
	return 1;
}

int main(){
	int cs; cin >> cs;
	while(cs--){
		int n, p, q; cin >> n;
		
		for(p = n + 1; !isprime(p); p--);
		for(q = p + 1; !isprime(q); q++);
		
		ll a = (p - 2ll) * q + (n + 1ll - p) * 2;
		ll b = 2ll * p * q;
		ll g = __gcd(a, b);
		a /= g; b /= g;
		cout << a << "/" << b << endl;
	}
	return 0;
}