atcoder ABC110 D問題

今回は方針は数学的な問題だったが全くできなかった。
https://atcoder.jp/contests/abc110/tasks/abc110_d

方針

まず素因数分解を考える。MについてM = p₁^q₁ p₂^q₂p₃^q₃　と表せた時、M=a₁a₂a₃の組み合わせは、それぞれのp_iについて、q_i+N-1の中からq_iを選ぶ組み合わせの数の積となる。また、今回は、答えについて1000000007で割ったあまりを求めるという操作がある。普通、足し算や引き算や掛け算ではさほど問題ではないが、割り算の時の場合、計算結果が変わる可能性も多いにあるので、ただ単にmodで割るわけにはいかない。ここで逆元を使う。

逆元

b/a ≡ b*a^p-2 (mod 1000000007)
これによって正確に値を求めることができる。なおpがmodとなり桁がすごいことになるので、aのp-2乗を素早く求める必要がある。そこで、二分累乗というテクニックを使う。

二分累乗

aのx乗を求める際に、再帰を使うことで高速に求めるテクニック。実装例は以下の通り、

static long modpow(long a,long p){
        if(p == 0){
            return 1;
        }
        if(p % 2 == 0){
            long halfp = p/2;
            long half = modpow(a, halfp);
            return half*half%pow;
        }else{                       //桁が奇数の時の調整
            return a*modpow(a, p-1)%pow;
        }
    }

参考url