yukicoder No.136 Yet Another GCD Problem

問題はこちら
No.136 Yet Another GCD Problem - yukicoder

配列AがNの分割であるとき、gcd(A)はAの各要素を割り切るのでもちろんその合計Nも割り切る。
よって任意の分割に対しgcd(A)はNの約数となる。
|A|≧2なのでgcd(A)≠Nだから、gcd(A)の候補の最大値は、Nの約数の内Nでない最大のもの。
これをdとすると実際に{d,N-d}という分割によりこれを達成できるのでこれが答え
Kの値はいらない。

N≦100000なので順に割っていけば良い

int main(){
	int n,i;
	scanf("%d",&n);
	for(i=n-1;n%i;i--);
	printf("%d",i);
	return 0;
}

1より大きな最小の約数iを求めてN/iを出力することにして短縮

n;
main(i){
	for(scanf("%d",&n);n%++i;);
	n=!printf("%d",n/i);
}

58B