SRM 473 Div2 Hard ChildlessNumbers

問題

http://apps.topcoder.com/wiki/display/tc/SRM+473

自然数Xの桁ごとの数の和をD(X)とする。X / D(X)が割りきれる時これをYとし、YはXの親、XはYの子と呼ぶことにする。自然数AからBの間に子のない自然数はいくつあるか。

やりかた

制約にB - A <= 10000 とあるのでこれを使う。
A ~ Bの間の自然数を一つとりだしてみる（Cとする）。これが子を持つときX / D(X) = CなるXが存在するので、X = C * D(X)と変形できる。
あとはD(X)を適当な大きさまでループを回してみて変えてみて、D(C * D(X)) = D(X)となればこの数字は子を持つとわかる。こうしてCをAからBまで変化させて子を持たないものの数を数えればいい。

計算量の見積が難しい。

以下ソース。

class ChildlessNumbers {
public:
  ll D(ll a){
    ll ret = 0;
    while(a){
      ret += (a % 10);
      a /= 10;
    }
    return ret;
  }
  int howMany(int A, int B) {
    int result = 0;
    for(ll i = A; i <= B; i++){
      bool isok = false;
      for(ll j = 1; j <= 500; j++){
	if(D(i * j) == j){
	  isok = true;
	  break;
	}
      }
      if(!isok) result++;
    }
    return result;
  }
};

D(X)を1000までループを回してみたら１ケースのみTLEした。500にしたら通った。

（追記）
X = Y * D(X)でY <= 10^9 なのでX <= 10^9。
だからD(X) <= 9 + 9 * log10(X) < 100となるから１００くらいまでのループでいいようだ。