题解 | #整除问题#

对两个数都分解质因数，质因数和指数对存在vector里，然后用小的vector去攻击大的vector，一比一扣血，每扣一次k++

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

//读题：即n！的因子中恰有k个a，求出这个k  a，n是给定的，所以这个“最大的k”是一个多余描述 
//所以事实上就是对n！做因子分解，注意a可以是合数 
//理论上暴力解法是很快的。问题在于不能真的去算1000！，太大了！得每个数去看 

//感觉可以对n和a各自分解质因数，存进vector里 利用质因数分解结果的唯一性来得到答案 靠谱

class Pair68{//质因数和指数对 
public:
	int index;
	int p;
	int e;//exp
	Pair68(int ii, int pp, int ee):index(ii),p(pp),e(ee){}
}; 

vector<Pair68> vnj;//存n！的分解质因数结果 
vector<Pair68> va;//存a的分解质因数结果 

int main(){
	int l=(int)sqrt(1000); 
	bool Isprime[l];
	fill(Isprime, Isprime+l, true);
	vector<int> prime;
	for(int i=2; i<l; i++){
		if(Isprime[i] == false){
			continue;
		}else{
			prime.push_back(i);
			for(int j=i*i; j<l; j+=i){
				Isprime[j] = false;
			}
		}
	}
	int a, n;
	while(scanf("%d%d",&n,&a) != EOF){//先不做非法输入检查了
		//vnj需要预先分配并初始化，va不需要
		for(int i=0; i<prime.size(); i++){
			vnj.push_back(Pair68(i,prime[i],0));
		}
		int maybe = 0;//可能大于根号n！的那个质因数 
		for(int i=2; i<=n; i++){//先对n！分解质因数
			int itmp = i;
			for(int j=0; j<prime.size(); j++){
				if(prime[j]>i){
					break;
				}
				while(itmp%prime[j]==0){//利用好：prime下标对应着质数的序号 
					vnj[j].e++;
					itmp /= prime[j];
				}
			}
			//如果itmp还有剩，那必也是一个质数 就是找他的位置有点烦又要遍历 
			if(itmp>1){
				int zhaodao = 0;
				for(int m=0; m<prime.size(); m++){
					if(prime[m] == itmp){
						vnj[m].e++;
						zhaodao = 1;
						break;
					}
				}
				if(!zhaodao){
					maybe = itmp;
					vnj.push_back(Pair68(0,maybe,1));
				}
			}
		}
		//再对a分解质因数
		int atmp = a;
		for(int j=0; j<prime.size(); j++){
			int exp = 0;
			if(prime[j]>a){
				break;
			}
			while(atmp%prime[j]==0){//利用好：prime下标对应着质数的序号 
				exp++;
				atmp /=prime[j];
			}
			if(exp){
				va.push_back(Pair68(j,prime[j],exp));
			}
		}
		if(atmp>1){
			if(atmp == maybe){
				va.push_back(Pair68(vnj.size()-1,atmp,1));
			}else{
				printf("Error\n");
				exit(0);
			}
		}
		int k = 0;
		//用va 去 攻击 vnj 一比一换血 
		int bk = 0;
		while(1){
			for(int i=0; i<va.size(); i++){
				if(vnj[va[i].index].e == 0){//没得扣了，血扣完了 
					bk = 1; 
					break;
				}
				va[i].e--;
				vnj[va[i].index].e--;
			}
			if(!bk){//成功扣掉一组 
				k++;
			}else{
				break;
			}
		}
		printf("%d\n",k);
		vnj.clear();
		va.clear();
	} 
	return 0;
}