文章

60

粉丝

361

获赞

43

访问

524.6k

头像
简单思路
P1284 上海交通大学机试题
发布于2021年1月17日 10:18
阅读数 9.2k

思路:

1、对N!分解质因数,所以分别对1、2、3……N分解质因数,然后用一个数组下标记录该质因数的个数

2、对a分解质因数,然后计算相同质因数下,1步质因数个数除以2步质因数个数的最小值即为所求

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000;
int prime[2][maxn];
void getPrime() {
	memset(prime, 0, sizeof(prime));
	for (int i = 2; i <= maxn; i++) //输入数
	{
		if (!prime[0][i]) //未被动过,每个数赋值i prime[0]存的是素数的个数
			prime[0][++prime[0][0]] = i;

		for (int j = 1; j <= prime[0][0] && prime[0][j] * i <= maxn; j++) 
		{
			prime[0][prime[0][j] * i] = 1;//素数倍数不是素数
			if (i % prime[0][j] == 0)	break;
		}
	}
}
int main()
{
	int n,a;
	int b[1000]={0};
	while(cin>>n>>a)
	{
		getPrime();//做出N内的质因数
		for(int k=2;k<=n;k++)//N个数
		{
			int num=k;
			//对每个数分解质因数
			for(int i=1;i<=prime[0][0];i++)
			{
				while(num%prime[0][i]==0)
				{
					num=num/prime[0][i];
					prime[1][i]++;//记录质因数个数
				}
			}
		}
		//对a分解质因数
		for(int i=1;i<=prime[0][0];i++)
		{
			while(a%pr...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发