Edited at

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