お断り：提出してないので間違ってるかも
O(N^0.75) prime countingを完全に理解していてこれが解けないのは端的に言ってカスなんだよね
・そもそもφはmultiplicativeなので、当然素因子ごとにわけて考えたくなる
・dp[i][j]=#{n | nの全ての素因子はPi以下、φ(n)=j}としてDPできる
遷移はdp[i-1][j]からdp[i][j*(Pi-1)*Pi^k]に配れば良い
・第2添字には乗算しか登場しないので、「あと何倍したらNを超えるか」しか情報がいらない。平方根で分けるテクで状態数がO(√N)になる
・in-placeに更新することにすると、O(N^0.75) prime counting とほとんど同じ計算量解析により、p*(p-1)≦Nを満たす素数p=O(√N)までO(N^0.75)で計算できることがわかる
・それ以降の素数は高々1個しか含まれないので、各pに対してφ(x)≦N/(p-1)となるxの個数がわかればよい（そしてこれは既に計算済み）
・N/(p-1)は小さいので、pごとではなく、N/(p-1)ごとにまとめて計算すれば高々O(√N)。N/(p-1)=kとなるようなpの個数はO(N^0.75) prime countingを実行すると副産物として手に入っている。（境界が1個ずれてる分はいちいちチェックすれば良い）
・よって解けた
