問題はこちら
No.677 10^Nの約数 - yukicoder
約数は2^i*5^jの形をしている。全て求めてソートすればよい。
ここでは約数を保存せず、毎回「今まで出力したものより大きい最小のもの」を探すようにしている。O(N^4)
main(){
int n;
scanf("%d",&n);
long M=0;//直前に出力したもの
for(int cnt=0;cnt<(n+1)*(n+1);cnt++){
//約数は全部で(n+1)*(n+1)個
long m=2e18;//Mより大きな最小の約数(=次に出力するもの)
for(int i=0;i<=n;i++)for(int j=0;j<=n;j++){
long t=pow(2,i)*pow(5,j);
if(t>M&&t<m)m=t;
}
printf("%ld\n",m);
M=m;
}
}
まずざっと縮める
long M,m,t;i,j,x; main(n){ for(scanf("%d",&n);x++<~n*~n;printf("%ld\n",M=m)) for(m=2e18,i=0;i<=n;i++)for(j=0;j<=n;j++)(t=(t=pow(5,j))<<i)>M&t<m?m=t:0; }
for文をまとめる
for(m=2e18,i=0;i<=n;i++)for(j=0;j<=n;j++)(t=(t=pow(5,j))<<i)>M&t<m?m=t:0; for(m=2e18,i=0;j<=n?(t=(t=pow(5,j++))<<i)>M&t<m?m=t:1:(j=0,i++<n);); for(m=2e18,i=0;j>n?j=0,i++<n:(t=(t=pow(5,j++))<<i)>M&t<m?m=t:1;);
もう1つのfor文をまとめても短くならなかった
long M,m,t;i,j,x;main(n){for(scanf("%d",&n);x++<~n*~n;printf("%ld\n",M=m))for(m=2e18,i=0;j>n?j=0,i++<n:(t=(t=pow(5,j++))<<i)>M&&t<m?m=t:1;);} long M,m=1,t;i,j,x;main(n){for(scanf("%d",&n);j>n?j=0,i++>=n?i=!printf("%ld\n",M=m),m=2e18,++x<~n*~n:1:(t=(t=pow(5,j++))<<i)>M&&t<m?m=t:1;);}
何れにせよ140B
