kmjp's blog

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

yukicoder : No.276 連続する整数の和(1)、No.278 連続する整数の和(2)

4問目より3問目の方が手こずった。先4問目やった方がよかった…。
No.276は★2だけど、No.276の知見がNo.278で必要なので両方ここで扱います。
http://yukicoder.me/problems/744
http://yukicoder.me/problems/745

問題

No.276

正整数Nが与えられる。
「連続するN個の正整数の和はXで割り切れる」という命題を満たす最大の正整数Xを求めよ。

No.278

正整数Nが与えられる。
「連続するN個の正整数の和はXで割り切れる」という命題を満たす正整数Xの総和を求めよ。

解法

まずNo.276について考える。
1~Nの総和は \frac{N(N+1)}{2}である。
次に2~(N+1)の総和、3~(N+2)の総和…と考えていくと総和はNずつ増えていく。
よってXは GCD(N,\frac{N(N+1)}{2})と考えられる。
この最大公約数はNが奇数ならN、偶数ならN/2となる。

No.278は上記Xの約数の総和を求めればよい。
以下のコードは278用。

ll N;
ll ret;

void solve() {
	
	cin>>N;
	
	if(N%2==0) N/=2;
	
	for(ll a=1;a*a<=N;a++) if(N%a==0) {
		ret += a;
		if(a*a!=N) ret += N/a;
	}
	cout<<ret<<endl;
	
}

まとめ

276は何も考えず「奇数ならN、偶数ならN/2」と回答しちゃったんで、Writer解説の中央パートは全く意識しなかった。