SRM 540 Div2 Hard FractionInDifferentBases

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11135&rd=14732
P / Q（既約とは限らない）をX進数で表現した時に割り切れないとする。AからBの間にこのようなXはいくつ存在するか。

やりかた

Editorialを参考にしました。

まずP、Qをこれらの最大公約数で割って既約分数にしておく。
また、割り切れないものではなく割り切れるものの数を数えることにする。
割り切れるときは
$P \cdot X^i \equiv 0 \ (mod Q)$
を満たすようなiが存在するときである。たとえば P = 1, Q = 20, X = 10としたとき、P / Qは10進数で表現し、割り切れる。そして i = 2 が上の式を満たす。
ただ P、Q は既約分数にしたので互いに素であることから
$X^i \equiv 0 \ (mod Q)$
である。このようなXで最小のもの（Yとする）はQの素因数のみを掛けあわせたものになる。（たとえば Q = 24 = 2*2*2*3 なら Y = 2*3）
あとはこのYの倍数のものでかつA~Bに存在するものの個数を数える。A~B中でそれ以外のものが求める物の数になる。

以下ソース。

class FractionInDifferentBases {
public:
  map<ll, ll> prime_factor(ll n){
    map<ll, ll> ret;
    for(ll i = 2; i * i <= n; i++){
      while(n % i == 0){
	ret[i]++;
	n /= i;
      }
    }
    if(n != 1) ret[n] = 1;
    return ret;
  }

  long long getNumberOfGoodBases(long long P, long long Q, long long A, long long B) {
    long long result;
    ll g = __gcd(P, Q);
    P /= g;
    Q /= g;
    ll Y = 1; 
    map<ll, ll> pf = prime_factor(Q);
    map<ll, ll>::iterator it = pf.begin();
    for(; it != pf.end(); it++) Y *= it->first;
    ll finite = B / Y - (A - 1) / Y;
    return (B + 1 - A) - finite;
  }
};

f
$P \cdot X^i \equiv 0 \ (mod Q)$
ここが思いつきにくい。ただ割り切れるか否かの判定はこれからも出てきそうだし、覚えておきたい。