SRM 510 Div2 Hard TheLuckyBasesDivTwo - Area1のif(memo[i][j])

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11466&rd=14439
自然数nが与えられる。これをb進数で表した時に各桁に4か7しか現れないようなb進数（ただしb >= 2）はいくつか（つまりbはいくつの値を取りうるか）。

やりかた

全探索ではもちろん間に合わない。

nはli=4 or 7として $n=l_{n-1}b^{n-1}+l_{n-2}b^{n-2} + \cdots + l_1b^1+l_0b^0$ と表される。ここで小さい桁数の時を考えてみる。

n=1のとき

$n=l_0$ なのでこれは何進数であろうがl0は4か7のためluckyになってしまうので無限の答えがある。よって-1を返す。

n=2のとき

n= 4b + 4、4b + 7、7b + 4、7b + 7 のいずれかなのでこれを満たすbが適するbになる。ただし4b+4のときはbは4より大きくなければならず、4b+7、7b+4、7b+7のときはbは7より大きくなければならない。そうでないと進数の表現上おかしいことになる。

n>= 3のとき

たとえばn=3のとき $n=4b^2+4b+4$ などが成り立つbを調べたいわけだが、これが成り立つようなbはn <= 1e12 という制約上、どう考えてもb < √1e12 = 1000000 であるとわかる。そしてn>=3では調べるべきbの範囲はさらに小さくなる。なのでこのケースではbを1000000程度までループさせて調べれば十分である。

以下ソース。

class TheLuckyBasesDivTwo {
public:
  bool islucky(ll a, ll base){ // aのbase進数表現はluckyになるか？
    while(a){
      if(a % base != 4 && a % base != 7) return false;
      a /= base;
    }
    return true;
  }
  long long find(long long n) {
    set<ll> result;
    if(n == 4 || n == 7) return -1;
    if((n - 4) % 4 == 0 && (n - 4) / 4 > 4) result.insert((n - 4) / 4);
    if((n - 7) % 4 == 0 && (n - 7) / 4 > 4) result.insert((n - 7) / 4);
    if((n - 4) % 7 == 0 && (n - 4) / 7 > 7) result.insert((n - 4) / 7);
    if((n - 7) % 7 == 0 && (n - 7) / 7 > 7) result.insert((n - 7) / 7);
    for(ll i = 5; i * i <= n; i++) if(islucky(n, i)) result.insert(i);
    return result.size();
  }
};

これはできた。よかった。正解者もそれほど多くない問題でACできたので嬉しい。