CCF模拟_202312-2_因子化简（80%）

今天请务必休息一天 / 2024-01-26 / 原文

计算机软件能力认证考试系统

题目

样例输入

3
2155895064 3
2 2
10000000000 10

样例输出

2238728
1
10000000000

思路：

这个题主要麻烦的地方应该在于分解成素数n次方相乘的数学思想和大整数的处理。

关于素数分解，一个思路是简单粗暴地把小于n的所有素数都给尝试一遍（也只会暴力了😭）

比如说有这么一个数n，首先用2的1次方去除，能不能除尽？能的话用2的2次方去除，能不能除尽？然后继续......能不能用2的14次方去除？发现不能除尽！所以这个n至少可以被分解为

n=（2^13）*......（省略号是因为后边的还不知道）

然后n=n/(2^13)

接下来用下一个素数3，首先用3的1次方去除，能不能除尽？能的话用3的2次方去除，能不能除尽？然后继续......能不能用3的8次方去除？不能除尽！所以原来的那个n至少可以被分解为

n=（2^13）*（3^7）......

然后n=n/（2^13*3^7）

以此类推

这样的话n的分解倒是不难了，在运算中加入判定，比k小的变量不去管它，比k大或相等的变量乘进去就行了。

#include<iostream>
using namespace std;

//********判断一个数是否是素数********
bool is_prime(int a){
	if(a==2){
		return true;//a是素数
	}
	for(int i=2;i<=a/2;i++){
		if(a%i==0){
			return false;//存在不是1和它自身的因数，故不是素数
		}
	}
	return true;
}
//对一个数x开n次方
int nth_power(int x,int n){
	int r=1;
	for(int i=0;i<n;i++){
		r=r*x;
	}
	return r;
}

//********这个才是重点，已知n,k，返回n简化后的值
int Query_Results(long int n,int k){
	int Result=1;
	int j;
	for(int i=2;i<=n/2;i++){
		if(is_prime(i)==true){//如果i是素数
			j=1;
			while(nth_power(i,j)<=n){
				if(n%nth_power(i,j)!=0){
					break;
				}
				j++;
			}
			if(j-1>=k){
				Result=Result*nth_power(i,j-1);
				n=n/nth_power(i,j-1);
			}//筛选出大于k的因子
		}
	}
	return Result;
}



int main(){
	int q;
	long int **a;
	cin>>q;//第一行，输入q
	a=(long int**)malloc(sizeof(long int*)*q);//开辟q行空间
	for(int i=0;i<q;i++){
		a[i]=(long int*)malloc(sizeof(long int)*2);
	}//开辟空间存放接下来输入的数据
	for(int i=0;i<q;i++){
		cin>>a[i][0]>>a[i][1];
	}//输入接下来的数据，a[i][0]为n,a[i][1]为k
	
		
	//逐行输出
	for(int i=0;i<q;i++){
		cout<<Query_Results(a[i][0],a[i][1])<<"\n";
	}
	return 0;
}

n可能比较大，用传统的int或者long int啥的似乎存不下，这一部分测试样例满足不了（包括题中所给的那个样例输入就搞定不了），所以这个代码大概只能拿80分。