题解 | #整除问题#

//土尔逊Torson 编写于2023/05/13
#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "string.h"
#include "limits.h"
#include <vector>
#include <stdlib.h>

//质因数分解：
//把一个正整数数分解成几个质数的幂相乘的形式叫做质因数分解

using namespace std;

const int MAXN = 1000 + 100;

vector<int> prime07401;    //保存质数
bool isPrime07401[MAXN];   //标记数组

int N_arr[MAXN];
int A_arr[MAXN];
int Initial07401() {
	for (int i = 0; i < MAXN; ++i) {
		isPrime07401[i] = true;
	}
	isPrime07401[0] = false;
	isPrime07401[1] = false;
	for (int i = 2; i < MAXN; ++i) {
		if (!isPrime07401[i]) {  //非质数则跳过
			continue;
		}
		prime07401.push_back(i);
		if (i > MAXN / i) {      //只计算到 <= √MAXN
			continue;
		}
		for (int j = i*i; j < MAXN; j += i) {
			isPrime07401[j] = false;  //质数的倍数为非质数
		}
	}
	return prime07401.size();
}

void decompose_A(int a, int PrimeDivisor_len) { //对a进行质因数分解
	for (int i = 0; i < PrimeDivisor_len; i++) {
		int temp = prime07401[i];
		while (a%temp == 0) { //记录每个质因数的 次幂数 
			A_arr[temp]++;
			a /= temp;
		}
	}
}

void decompose_N(int n, int PrimeDivisor_len) { //对n进行质因数分解
	for (int i = 0; i < PrimeDivisor_len; i++) {
		int temp = prime07401[i];
		while (n%temp == 0) { //记录每个质因数的 次幂数 
			N_arr[temp]++;
			n /= temp;
		}
	}
}

int main() {
	int n, a;
	int PrimeDivisor_len = Initial07401(); 
	while (scanf("%d%d", &n, &a) != EOF) {
		memset(N_arr, 0, sizeof(int)*MAXN); //初始化 N_arr,A_arr 为 MAXN 大小的 0
		memset(A_arr, 0, sizeof(int)*MAXN);
		decompose_A(a, PrimeDivisor_len);//把a进行质因数分解
		for (int i = 2; i <= n; i++) {//把2~N进行质因数分解
			decompose_N(i, PrimeDivisor_len);
		}
		int k = INT_MAX;
		for (int i = 2; i < a; i++) { //a^k=a*a*a...*a(k个a相乘)
			if (N_arr[i] != 0 && A_arr[i] != 0) {//看把2~n分解的质因数中包含多少（倍的）a的质因数
				if (N_arr[i] / A_arr[i] < k) {//找最小次幂，是因为找最小公倍数的次幂 k 大于它的数 就是更大的整除次幂数
					k = N_arr[i] / A_arr[i];
				}
			}
		}
		printf("%d\n", k);
	}
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")