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

メモ

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

yukicoder No.276 連続する整数の和(1)

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

aから始まる連続するN個の自然数の和はaN+N(N-1)/2となる。
aは任意なのでGCD(N,N(N-1)/2)が求める答えになる(十分性は明らか。必要性はa=0,1から)

ところで
Nが奇数の時(N-1)は2で割り切れるのでN(N-1)/2はNの倍数でありGCD(N,N(N-1)/2)=N
Nが偶数の時(N-1)は2で割り切れないのでN(N-1)/2はNの倍数でない
しかしN=2mとおくとm(2m-1)となるのでmの倍数である。
mはNの自身を除く最大の約数であるから、GCD(N,N(N-1)/2)=m

まとめると求める答えは、Nが奇数の時N、偶数の時N/2となる

int main(){
	int n;
	scanf("%d",&n);
	printf("%d",n%2==0?n/2:n);
	return 0;
}

多分これが一番みじかいと思います

n;main(){n=scanf("%d",&n)>printf("%d",n/=2-n%2);}

49B