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

メモ

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

yukicoder No.339 何人が回答したのか

問題はこちら
No.339 何人が回答したのか - yukicoder

M人が回答し、選択肢iを選んだ人数をm[i]人とする。
m[i]たちの公約数が2以上なら、全体をそれで割ることでMを小さくできるので、m[i]たちは互いに素(setwise coprime)であるとしてよい。
m[i]/M*100=A[i]となるので、Mはm[i]*100の公約数であり、m[i]は互いに素なのでMは100の約数。
また100/Mをmとおくとm[i]*m=A[i]となるので、mはA[i]たちの公約数になる
Mの最小値を求めることはmの最大値を求めることと同値なので、結局a[i]たちの最大公約数を求めることになる

int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main(){
	int s=100,i,n;
	//a[i]たちの公約数は100の約数なので、初期値に100を与えておいて問題ない
	//(対偶から直ちに明らか)
	scanf("%d",&n);
	while(n--){
		scanf("%d",&i);
		s=gcd(s,i);
	}
	printf("%d",100/s);
	return 0;
}

縮める

s=100,t;main(i){for(;~scanf("%d",&i);t=1)for(i*=t;t=i;s=t)i=s%i;t=!printf("%d",100/s);}
//0かけてみた
s=100,i;main(t){for(gets(&t);i?t=i,i=s%i,s=t:~scanf("%d",&i););i=!printf("%d",100/s);}
//普通にgetsすればよくない?
s=100,i;main(t){for(gets(&t);i||~scanf("%d",&i);i=s%i,s=t)t=i;i=!printf("%d",100/s);}
//処理の中身をfor文の後ろにまわしても大丈夫

85B