読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.278 連続する整数の和(2)

問題はこちら
No.278 連続する整数の和(2) - yukicoder

前回の問題yukicoder No.276 連続する整数の和(1) - メモの考察から、σ1を約数関数として
Nが偶数の時σ1(N/2)、奇数の時σ1(N)となることが分かるのでこれを求める

int main(){
	long s=0,i,n,m;
	scanf("%ld",&n);
	if(n%2==0)n/=2;
	m=sqrt(n);
	for(i=1;i<m;i++)if(n%i==0)s+=i+n/i;
	//iがnの約数ならn/iもそう
	if(n%i==0)s+=i;
	//ただしnが平方数でiが√nの時に注意
	printf("%ld",s);
	return 0;
}

ぎゅっと

long s,n,i;
main(){
	for(scanf("%ld",&n),n/=2-n%2;n/++i/i;s+=n%i?0:n-i*i?i+n/i:i);
	i=!printf("%ld",s);
}

99B

解説のコメンタリにある
>少し気になりましたが σ(N) (N≤2×10^12) ってlong longに収まってますよね?
は次のようにして証明できる
K=\lceil\log{2}(N+1)\rceilとおいて
\begin{eqnarray*}
\sigma(N)&=&\sum_{i|N}\frac{N}{i}\\
&\leqq&\sum_{i=1}^{N}\frac{N}{i}\\
&\leqq&\sum_{i=1}^{2^K-1}\frac{N}{i}\\
&=&\sum_{k=0}^{K-1}\sum_{j=0}^{2^k-1}\frac{N}{2^k+j}\\
&\leqq&\sum_{k=0}^{K-1}\sum_{j=0}^{2^k-1}\frac{N}{2^k}\\
&=&\sum_{k=0}^{K-1}N\\
&=&NK
\end{eqnarray*}