PKU 2649-Factovisors

問題概要

n!がmで割り切れるか判定せよ

解法(C++)

コーナーケースゲー．n=0またはm=0に注意．
n!が素因数pで割り切れる回数はn/pを0になるまで繰り返すことで求めることが出来るので，
mを素因数分解して，n!に表われる回数以上か調べる．

実装(C++)

酷すぎる実装．

#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#define REP(i,x) for(int i=0;i<(int)x;i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
using namespace std;
const int sieve_max=65536; //予め計算しておく素数の最大値
vector<bool> eratosthenes_sieve(int n){
	vector<bool> res(n+1);
	res[0]=res[1]=false;res[2]=true;
	int i,j,m=sqrt(n)+1e-9;
	for(i=3;i<=n;i+=2){
		if(i<=m){
			if(res[i]==false){
				for(j=i+i+i;j<=n;j+=i+i){
					res[j]=true;
				}
			}
		}
		res[i]=!res[i];
	}
	return res;
}

vector<int> prime_list(const vector<bool>& isprime){
	vector<int> res;if(isprime.size()<=2)return res;
	res.push_back(2);
	for(unsigned int i=3;i<isprime.size();i+=2)
		if(isprime[i])res.push_back(i);
	return res;
}
vector<int> prime_list(int n){
	return prime_list(eratosthenes_sieve(n));
}
vector<int> primes=prime_list(sieve_max);
long long mod_pow(long long a,long long n,long long M){
	if(n==0)return 1;
	long long res=mod_pow(a*a%M,n/2,M);
	if(n&1)res=res*a%M;
	return res;
}
bool miller_rabin(long long n){
	if(n==2)return true;if((n&1)==0||n<=1) return false;
	int a[]={2,7,61,-1},r;long long s=0,d,x;
	d=n-1;
	while((d&1)==0)s++,d=d>>1;
	for(int i=0;a[i]!=-1&&a[i]<n;i++){
		if((x=mod_pow(a[i],d,n))!=1){
			for(r=0;r<s;r++){
				if(x==n-1)break;
				x=(x*x)%n;
			}
			if(r==s)return false;
		}
	}
	return true;
}
inline long long random(long long x,long long c,long long m){
	return (x*x%m+c)%m;
}
int constant[5]={1,51,73,0};
long long absll(long long v){
	if(v<0)return -v;
	return v;
}
void pollards_rho(long long v,vector<long long>& res,bool precheck=true){//resに素因数分解の結果が入る
	if(precheck){
		REP(i,primes.size()){
			while((v%primes[i])==0){
				v/=primes[i];
				res.push_back(primes[i]);
			}
		}
		if(v==1)return;
	}
	if(miller_rabin(v)){
		res.push_back(v);
		return;
	}
	long long x=2,y=2,d=1;

	for(int i=0;constant[i];i++){
		while(d==1){
			x=random(x,constant[i],v);
			y=random(random(y,constant[i],v),constant[i],v);
			d=__gcd(absll(x-y),v);
		}
		if(d==v)continue;;
		pollards_rho(d,res,false);
		pollards_rho(v/d,res,false);
		return;
	}
}
typedef long long lli;
//m!に素因数pはいくつ含まれるか
lli count(lli m,lli p){
	lli res=0;
	while(m){
		res+=m/p;
		m/=p;
	}
	return res;
}
bool solve(lli n,lli m){
	vector<lli> f;
	if(n==0)n=1;
	pollards_rho(m,f);
	map<int,int> s;
	REP(i,f.size()){
		s[f[i]]++;
	}
	FOR(it,s){
		if(count(n,it->first)<it->second)return false;
	}
	return true;
}
int main() {
	int n,m;
	for(;cin>>n>>m;){
		if(m!=0&&solve(n,m)){
			cout<<m<<" divides "<<n<<"!"<<endl;
		}else{
			cout<<m<<" does not divide "<<n<<"!"<<endl;
		}
	}
	return 0;
}