【CCF CSP】202312-2 因子化简(C/C++解题思路+满分题解)

解题思路

80分思路+代码

��       由于题目在数据规模中说明阈值k > 1, 因此提取因式时只需要关注次数在二次以上的因式。也就是说，我们只需要判断从1到待化简因式的平方根是否是满足题意的因式即可。举个例子，假设题目所给因式是10000，那么只需要判断从1到内是否存在10000的质因式即可，因为大于100的质因式一定会被舍去。

        再观察数据规模，如果输入的因式小于1*10^4，那么只需要判断从1到100的质因式即可。小学老师应该要求背过从1到100的质数吧，现在就派上用场了。

        首先读入查询组数, 定义待处理因式n, 阈值k和输出值output。定义一个质因数数集保存从1到101的27个质因数。定义一个哈希数组保存从1到100质因数的指数，并且在每次循环初始化哈希数组。

int q;
cin >> q;
int n, k, output;
int arr[27] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,93,97,101};
int temp[102];
for(int i = 0; i > n >> k;
...

        循环判断从1到101（为了保险）的27个质因数是否能整除待处理因式n。如果其中一个因数能整除待处理因式，那么将该因式从待处理因式分离并在哈希数组中记录该质因数的指数变化。并且继续判断该因数能否被整除，直到出现余数。

        此时需要看该质因数的指数是否达到阈值。如果达到，将相应次数的质因数与输出output相乘。当待处理因式只剩下1的时候，退出循环，输出output。

for(int j = 0; j = k)
		output *= pow(arr[j], temp[arr[j]]);
	if(n == 1)
		break;
	j++;
}
cout  q;
    
    for(int i = 0; i > n >> k;
        for(int j = 0; j = k)
		        output *= pow(arr[j], temp[arr[j]]);
	        if(n == 1)
		        break;
            j++;
        }
        cout > n >> k;
        if(n > 10000)
        {
            multiset division; 				//分离后的因式
            division = divide(n);
            memset(longtp, 0, sizeof(int)*10002);	//每次都要初始化所有指数为0
            for(auto it = division.begin(); it != division.end(); it++)
                cal(*it);							//计算所有因式
            for(int j = 2; j = k)
                    output *= pow(j, longtp[j]);
        }
        else
        {
            memset(temp, 0, sizeof(int)*102);
            for(int j = 0; j = k)
                    output *= pow(arr[j], temp[arr[j]]);
                if(n == 1)
                    break;
                j++;
            }
        }
        cout