Codeforces #829 : Div1 B. Factorial Divisibility

早解き回で解くのが遅かったため微妙な出来に。
https://codeforces.com/contest/1753/problem/B

問題

N個の整数列A[i]と整数Xが与えられる。

A[i]の階乗を取ったA[i]!の総和がX!の倍数であるか判定せよ。

解法

階乗進数を考え、X!以下の桁が0になるか、下の桁から繰り上がりを考えて行けばよい。

int N,X;
ll M[505500];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	map<int,int> M;
	FOR(i,N) {
		cin>>x;
		M[x]++;
	}
	for(i=1;i<X;i++) {
		M[i+1]+=M[i]/(i+1);
		if(M[i]%(i+1)) {
			cout<<"No"<<endl;
			return;
		}
	}
	cout<<"Yes"<<endl;
	
}

まとめ

まぁこれは簡単だね。