【CCF CSP】202312-2 因子化简

1. 题目要求

2. 前提

①算术基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。
②质数：除了1和它本身，没有别的数可以整除它。（1不是质数，2是质数）

3. 思想

将n分解成的不同素因子相乘的形式，当某一个素因子的个数≥k时，就保留下来，即temp *= pow(i,t);

问题是，如何分解呢？
最简单的方法是，i从2到n进行遍历，若是能整除n，则输出i，并且n=n/i。

注1：我看其他大佬的代码都没有判断i是否质数，应该是因为不需要，例如，若2为其质因子，全部输出后，则当i=4时，就不可能再整除n了。
注2：若n本身为质数 或者 n的某个质因子的对应的指数为1，则i遍历之后，n>1；否则n=1. （例如17，14，28，反例25）

但为了提高时间效率，可以从多个方面进行改进：

改进点1：质因子的最大值不超过n的平方根+1（例如6=2*3）
改进点2：质因子除了2之外，只能是奇数（感觉对时间复杂度的改进不大，反而使代码看起来更丑陋了）

最终代码如下所示。

3. 代码

#include <iostream>#include <cstdio>#include <cmath>#include <vector>using namespace std;long long primeFactor(long long n, long long k){    int t = 0;//素数因子的阶数    long long temp = 1;//记录最终返回值    // 除去所有 2 的倍数的因子    while(n % 2 == 0){        t++;        n /= 2;    }    if(t>=k){        temp = powl(2,t);    }    // 经过第二步, 此时 n 一定为奇数    // 并且不存在偶数的素因子    // 所以我们可以跳过所有偶数 (i += 2)    for(int i = 3; i <= sqrt(n); i += 2){        //除去所有 i 的倍数的因子        t=0;        while(n % i == 0){            t++;            n /= i;        }        if(t>=k){            temp *= powl(i,t);        }    }    //此处为了防止剩下的素因子是一个大于 2 的素数    if(n > 2){        if(k<=1)            temp *= powl(n,t);    }    return temp;}int main(){    int hang;    cin >> hang;    vector<vector<long long> > arr(hang,vector<long long>(2));    for(int i=0; i < hang; i++){        cin>>arr[i][0];        cin>>arr[i][1];    }    for(int i=0; i < hang; i++){        cout << primeFactor(arr[i][0],arr[i][1])<<endl;    }    return 0;}

6是如何分解的？
首先除去2，n=3，所以2为一个质因子；
由于3<根号3，所以跳过循环；
由于n>2,所以另一个质因子为3.

4. 结果

5. 总结

写代码时，遇到几个bug
①对于32位编译器，int和long都是用4个字节表示的；对于64位编译器，long是用8个字节表示的。所以我最开始用long表示，2155895064这个测试输入数据超出其表示长度了。
②pow(x,y)：求x的y次幂，但是由于是double类型的，截断小数部分之后，某些值的结果与实际值总是相差1。 换成powl(x,y)之后，就正常了。

6. 参考代码

①
https://blog.csdn.net/m0_74172965/article/details/135090693?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1-135090693-blog-134935729.235%5Ev40%5Epc_relevant_3m_sort_dl_base2&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1-135090693-blog-134935729.235%5Ev40%5Epc_relevant_3m_sort_dl_base2&utm_relevant_index=2
②
https://www.cnblogs.com/1pha/p/7749828.html#:~:text=%E5%AF%B9%E4%BA%8E%E6%B1%82%E4%B8%80%E4%B8%AA%E6%95%B0%20n%20%E7%9A%84%E6%89%80%E6%9C%89%E8%B4%A8%E5%9B%A0%E5%AD%90%2C%20%E9%80%9A%E5%B8%B8%E6%98%AF%E5%9C%A8%20%5B2%2C%20sqrt%20%28n%29%5D%20%E7%9A%84%E8%8C%83%E5%9B%B4%E5%86%85%E6%9E%9A%E4%B8%BE,%E4%BB%A5%E5%8F%8A%20n%20%2F%20i.%20%E7%84%B6%E8%80%8C%2C%20Vishwas%20Garg%E6%8F%90%E4%BE%9B%E4%BA%86%E4%B8%80%E7%A7%8D%E6%9B%B4%E4%B8%BA%E9%AB%98%E6%95%88%20%28logN%29%E7%9A%84%E6%B1%82%E4%B8%80%E4%B8%AA%E6%95%B0%E6%89%80%E6%9C%89%E7%B4%A0%E5%9B%A0%E5%AD%90%E7%9A%84%E6%96%B9%E6%B3%95.
③
https://blog.csdn.net/LZXloveGYD/article/details/71340090?spm=1001.2101.3001.6650.4&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-4-71340090-blog-109158648.235%5Ev40%5Epc_relevant_3m_sort_dl_base2&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-4-71340090-blog-109158648.235%5Ev40%5Epc_relevant_3m_sort_dl_base2&utm_relevant_index=9

本文链接：https://www.kjpai.cn/news/2024-04-03/153324.html，文章来源：网络cs，作者：焦糖，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！