AtCoder
java8

atcoder ABC110 D問題

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

方針

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

逆元

b/a ≡ b*ap-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

https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#4-%E7%B4%AF%E4%B9%97-an