Submission #3711966

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#include <iomanip>
#define fi first
#define se second
#define fcout(n) cout<<fixed<<setprecision((n))
#define cinl(str) getline(cin,(str))
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=1000000007;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };



int main() {
	int n;
	cin >> n;
	map<int,int> m;
	int p=0,q=0,r=0,s=0,t=0;
	int ans;
	
	for(int i=2;i<n+1;i++){
		int x=i;

		for(int j=2;j*j<n+1;j++){
			while(x%j==0){
				//素因数jの数をカウント
				m[j]++; 
				x /= j;
			}
		}

		//nが小さいときの数え漏れ防止
		if( x!= 1) m[x]++;

	}

	for(int i=2;i<n+1;i++){
		//p^74
		if(m[i]>=74) p++;
		//p^24
		if(m[i]>=24) q++;
		//p^14
		if(m[i]>=14) r++;
		//p^4
		if(m[i]>=4) s++;
		//p^2
		if(m[i]>=2) t++;
	}

	//(p^74の数)+(p^24*q^2の数)+(p^14*q^4の数)+(p^4*q^4*r^2の数)
	//自身を選んだり、(p,q),(q,p)を別のものと数えないようにする
	//((pの数)*(p以外のqの数)*t)/2(pとqを入れ替えたもの重複分)-((pの数)*(p以外のqの数)分p,qからtを選んでしまった分)
	ans = p + (q*t-q) + (r*s-r) + (s*(s-1)*t-2*s*(s-1))/2;
	cout<<ans<<endl;

}

Submission Info

Judge Result