2023-12-2、因子化简-526互联

注意数据类型不要溢出

//因子化简
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

//判断是否是素数
bool is_prime(int num)
{
    if(num<=1)
        return false;
    if(num==2)
        return true;
    for(int i = 2; i<=(int)sqrt(num)+1;i++)
    {
        if (num%i==0)
        {
            return false;
        }
        
    }

    return true;
}

int main()
{
    vector<int> ss;
    vector<int> r;
    vector<long long> p;
    long long num = 1;
    int q;//q个查询
    //n设置成longlong类型，否则测试数据溢出
    long long n, k;//需化简的正整数n和阈值k

    cin>>q;

    //2到10^10的所有素数
    for(int i = 2; i<=100000; i++)
        if (is_prime(i))
        {
            ss.push_back(i);
        }
    
    while(q--!=0)
    {
        r.clear();//清空
        int result[100000]={0};
        num = 1;

        cin>>n>>k;
        for(int i = 0; i<ss.size(); i++)
        {
            while(n%ss[i]==0)//可以被该素数整除
            {
                r.push_back(ss[i]);//存放素数
                n/=ss[i];
            }

            if(n==1)
                break;
        }

        //化简
        for(int i = 0; i<r.size(); i++)
            result[r[i]]++;

        for(int i = 0; i<100000; i++)
            if(result[i]>=k)
            {
                for(int j = 0; j<result[i]; j++)
                    num*=i;
            }
        p.push_back(num);
    }

    for(int i = 0;i<p.size();i++)
        cout<<p[i]<<endl;

    return 0;
}

因子