なぜ高橋君は母親に数列を上げようとしたの…
一体その数列で何をするの…
なんかそういう本ないだろうか…
問題の条件から必要な型は long long
この問題の答えになる数列の条件は
- 1 <= X<= A <= Y <= 1018
- すべて整数
- A[i+1] = A[i] * 2
- A[i+1] > A[i]
1018 = 1,000,000,000,000,000,000なので、
型はlong long(9,223,372,036,854,775,807)である必要がある。
小さい数から計算していく
X = 3, Y = 20のときなら
小さい数は3。
この次の倍数は 6。
6倍数は12… と入れていく。
ある地点でYを超える。のでその直前まで計算する。
最小値以外のものを探る意味はない(一番数値の種類が多いものが、おのずと最大値になる)。
自分はなぜTLE*1になったのか
TYPE anser(const TYPE&x, const TYPE&y) { if( x >= y ) return 1; TYPE a = 0,b = x; for(TYPE i=x;i<=y;++i) { if( i % b > 0 ) continue; ++a; b = i; } if(a<=0) return anser(x+1,y); return a; };
上を見ればわかるだろうが…いちいち割り算使ってチェックしていたため。
そんなことしなくても、iを倍々にすればよかった。
*1:実行時間制限超過