murnana's diary

プリントの裏に書くとか、そんな感じです

ABC 083 C - Multiple Gift

C - Multiple Gift

なぜ高橋君は母親に数列を上げようとしたの…
一体その数列で何をするの…

なんかそういう本ないだろうか…


問題の条件から必要な型は 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:実行時間制限超過