atcoder ABC114 D問題

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

考え方

問題は、N!の約数のうち、ちょうど75個の約数を持つ数の個数を求める問題である。まずN!の約数について考えてみる。N! = p₁^q₁ p₂^q₂p₃^q₃と表せるとすると、N!の約数は(q₁+1)(q₂+1)(q₃+1)通りあることがわかる
(例) 4! = 24 = 2³ * 3 ->1,2,3,4,6,8,12,24 -> (4 * 2)=8個

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