ＡＢＣ１１４ D - 756

初めに思いついたこと：

・１００！を愚直に扱うのはまずい。（１５０桁くらいある）

・約数の個数なので、素因数分解した値を考えれば良さそう。

（この時、１００！を素因数分解しても、素因数の個数は（２＾１０）＾５０≒１０＾１５０よりせいぜい５００くらい。（余裕で扱える））

・N!=2^p2*3^p3*5^p5....の時、約数の個数は(p2+1)*(p3+1)*(p5+1)....となるのでこれを使えば約数７５個の条件もチェックできる。

mathtrain.jp

具体的には：

約数の個数が７５＝３＊５＊５=１５＊５＝３＊２５のとき、条件を満たす数はa^74またはa^2*b^4*c^4またはa^14*b4またはa^2*b^24のいずれかで表される。

よって、Ｎ！の素因数の個数をカウントしておけば、~乗になりうるかどうかがそれぞれ判定でき、素因数全体について全探索をすれば答えが求まる。

（素因数の種類はたかだか１００、なぜなら１０１以上の素数は１００！と互いに素である）

素因数の個数のカウントの仕方は、２～Ｎをそれぞれ素因数分解して、足し合わせていくだけ。

注意点：

a^4*b^4*c^2のとき、a<bなどの条件をつけてあげないと重複して数え上げてしまう。

私は条件の付け方を、for(i=2~){for(j=i+1~)}}のようにjについて、j=i+1スタートにした。

また、a,b,c（あるいはa,b）について、a==b||b==c||c==a == true　にならないように気を付けたい。明らかに条件が成立しなくなる。

例）２＾４＊３＾４＊２＾２＝２＾８＊３＾４　－＞　９＊５＝４５個　Ｘ

実装：

#include <bits/stdc++.h>
using namespace std;
#define int long long

map<int, int> res; // map[i]:=N!を素因数分解したときiは何乗か。

//Ｏ(√n)
//素因数分解
void prime_factor(int n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) {
        res[i]++;
        n /= i;
      }
    }
  }
  if (n != 1) {
    res[n]++;
  }
}

signed main() {
  int N;
  cin >> N;

  //Ｎ！の各要素を素因数分解し、足し合わせる。
  for (int i = 2; i <= N; i++) {
    prime_factor(i);
  }

  int ans = 0;

  //a^4*b^4*c^2
  for (int i = 2; i <= N; i++) {
    for (int j = i + 1; j <= N; j++) {
      for (int k = 2; k <= N; k++) {
        if (i == j || j == k || k == i) continue;
        if (res[i] >= 4 && res[j] >= 4 && res[k] >= 2) ans++;
      }
    }
  }

  //a^14*b^4 または a^24*b^2
  for (int i = 2; i <= N; i++) {
    for (int j = 2; j <= N; j++) {
      if (i == j) continue;
      if (res[i] >= 14 && res[j] >= 4) ans++;
      if (res[i] >= 24 && res[j] >= 2) ans++;
    }
  }

  //a^74
  for (int i = 2; i <= N; i++) {
    if (res[i] >= 74) ans++;
  }

  cout << ans << endl;
  return 0;
}

本番ではa^4*b^4*c^2の場合しか考えていなかった。

全体的に悔しいコンテストでした。

精進します。