問題はこちら
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