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

前回の問題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*}$