Posted at

atcoder ABC114 D問題

ABC114 C問題の解法をメモ

以前に階乗をべき乗で考えて約数を考える問題をやったことがあったがその考えを思い浮かべることができず全くできなかった。

https://atcoder.jp/contests/abc114/tasks/abc114_d


考え方

問題は、N!の約数のうち、ちょうど75個の約数を持つ数の個数を求める問題である。まずN!の約数について考えてみる。N! = p1q1 p2q2p3q3と表せるとすると、N!の約数は(q1+1)(q2+1)(q3+1)通りあることがわかる

(例) 4! = 24 = 23 * 3 ->1,2,3,4,6,8,12,24 -> (4 * 2)=8個

これで、約数の列挙はできたので、この中からちょうど約数が75個の数をカウントしていく。先ほどと同じ考え方で考えると約数を75個持つというのは、75の約数が{1,3,5,25,75}であるので、(qiの中で、75以上の個数)+((qiの中で、25以上の個数)(qiの中で、3以上の個数-1)) + ((qiの中で、15以上の個数) *(qiの中で、5以上の個数-1))+((qiの中で、5以上の個数)(qiの中で、5以上の個数-1)/2*(qiの中で、3以上の個数-1))

となる。

ちなみに、N以下の素数調べは以下の通り

ArrayList<Integer> list = new ArrayList<Integer>();

for(int i= 2; i <= n;i++){ //素数調べ
boolean flag = true;
for(int j = 2;j*j < i;j++){
if(i%j == 0){
flag = false;
break;
}
}
if(flag){
list.add(i);
}
}