Submission #3706086

---

Source Code Expand

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

map<int,int> prime_factor(int n) {
  map<int,int> ret;
  for (int i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ++ret[i];
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

vector<int> d(101,0);
int c_2, c_4, c_14, c_24, c_74;

signed main() {

  int N;
  cin >> N;

  for (int i = 1; i <= N; ++i) {
    auto p_f = prime_factor(i);
    for (auto itr=p_f.begin(); itr!=p_f.end(); ++itr) {
      d[itr->first] += itr->second;
    }
  }

  for (auto& e : d) {
    if (e >=  2)  c_2++;
    if (e >=  4)  c_4++;
    if (e >= 14) c_14++;
    if (e >= 24) c_24++;
    if (e >= 74) c_74++;
  }

  int res = 0;
  // a^2 * b^4 * c^4 -> C(c_4,2) * (c_2 - 2)
  res += max(0,c_4*(c_4-1)/2*(c_2-2));
  // a^2 * b^24 -> c_24 * (c_2 - 1)
  res += max(0,c_24*(c_2-1));
  // a^4 * b^14 -> c_14 * (c_4 - 1)
  res += max(0,c_14*(c_4-1));
  // a^74
  res += c_74;
  cout << res << endl;

}

Submission Info

Judge Result