kmjp's blog

競技プログラミング参加記です

Codeforces #232 Div1. B. On Sum of Fractions

Codeforces

昔読んだ学習漫画の知識が活きた…。
http://codeforces.com/contest/396/problem/B

問題

自然数nに対し、v(n)はn以下の最大の素数、u(n)はnより大きな最小の素数を表すとする。
nに対し\sum_{i=2}^n \frac{1}{v(n)u(n)}を求めよ。

解法

v(x) <= n < u(x)となるnでは、常に1/v(n)u(n)は一定である。
ここで上記総和の式がどうなるか見てみると、 \frac{1}{2\times 3} + \frac{2}{3\times 5} + \frac{2}{5\times 7} + ... + \frac{i}{v(i)u(i)} + ...となっている。
ここで、 \frac{i}{v(i)u(i)} = \frac{1}{v(i)} - \frac{1}{u(i)}であることを考えると1/3同士、1/5同士、1/7同士…が足し引きで消えていくことがわかる。

結局残るのは最初の項と最後の項だけなので、 \frac{1}{2} - \frac{1}{v(n)} + \frac{n-v(n)+1}{v(n)u(n)} = \frac{v(n)u(n) - 2u(n) + 2(n-v(n)+1)}{v(n)u(n)}が答え。

v(n)とu(n)はnから１ずつ数字を増減させて素数判定すれば間に合う。

ll isprime(ll a) {
	for(ll b=2;b*b<=a;b++) {
		if(a%b==0) return 0;
	}
	return 1;
}

void solve() {
	int f,i,j,k,l,x,y;
	int T;
	
	cin>>T;
	while(T--) {
		ll N,L,M;
		cin>>N;
		L=N,M=N+1;
		if(isprime(M)) {
			_P("%lld/%lld\n",M-2,2*M);
			continue;
		}
		while(isprime(L)==0) L--;
		while(isprime(M)==0) M++;
		ll aa=L*M-2*M+2*(N-L+1);
		ll bb=2*L*M;
		ll g=__gcd(aa,bb);
		_P("%lld/%lld\n",aa/g,bb/g);
	}
	
}

まとめ

\frac{b-a}{ab} = \frac{1}{a} - \frac{1}{b}という関係を昔読んだ学習漫画で覚えていたのが、ここで役に立った。