ccfcsp 202312-2 因子化简

3
2155895064 3
2 2
10000000000 10

2238728
1
10000000000

#include <bits/stdc++.h>
using namespace std;
const long long int maxn = 100005;
long long int n, k;
long long int q;
pair<long long int, long long int> tp[maxn];
long long int zhishu[maxn];
bool check(long long int a)
{
    if (a == 1 || a == 0)
        return false;
    for (long long int i = 2; i < a; i++)
    {
        if (a % i == 0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    cin >> q;
    long long int u = 0;
    for (long long int i = 1; i <= maxn / 2; i++) //0-u
    {
        if (check(i))
        {
            zhishu[u] = i;
            u++;
        }
    }
    for (long long int pp = 0; pp < q; pp++)
    {
        cin >> n >> k;
        long long int count = 0;
        for (long long int j = 0; j < u; j++)
        {
            if (n % zhishu[j] == 0)
            {
                long long int yc = 0;
                while (n % zhishu[j] == 0)
                {
                    yc++;
                    n = n / zhishu[j];
                }
                tp[count].first = yc;
                tp[count].second = zhishu[j];
                count++;
            }
            if (n == 1)
            {
                break;
            }
        }
        long long int ans = 1;
        for (long long int j = 0; j < count; j++)
        {
            if (tp[j].first >= k)
            {
                ans = ans * pow(tp[j].second, tp[j].first);
            }
        }
        cout << ans << endl;
    }
}

#include <bits/stdc++.h>
using namespace std;
long long int n, k, q;
vector<long long int> zhishu;
bool check(long long int num)
{
  if (num == 1)
    return false;
  if (num == 2)
    return true;
  for (long long int i = 2; i < num; i++)
  {
    if (num % i == 0)
      return false;
  }
  return true;
}
void iszhishu()
{
  zhishu.push_back(1); // 以1开头，质数在begin()+1,end()-1中
  for (long long int i = 2; i <= 1000; i++)//这里缩到1000以内，因为没有很大的数据
  {
    if (check(i))
      zhishu.push_back(i);
  }
  // for (vector<long long int>::iterator it = zhishu.begin(); it != zhishu.end(); it++)
  // {
  //   cout << *it << endl;
  // }
}
int main()
{
 
  cin >> q;
  iszhishu();
  while (q--)
  {
    cin >> n >> k;
    vector<pair<long long int, long long int>> shu; // t,p
    for (vector<long long int>::iterator it = zhishu.end() - 1; it != zhishu.begin(); it--)
    {
      if (n % (*it) == 0)
      {
        long long int u = 0;
        while (n % (*it) == 0)
        {
          u++;
          n /= (*it);
        }
        shu.push_back(make_pair(u, (*it)));
      }
    }
    sort(shu.begin(), shu.end());
    for (vector<pair<long long int, long long int>>::iterator it = shu.begin(); it != shu.end(); it++)
    {
      if ((*it).first < k)
      {
        (*it).first = 0;
      }
      // cout << (*it).first << " " << (*it).second << endl;
    }
    long long int ans = 1;
    for (vector<pair<long long int, long long int>>::iterator it = shu.begin(); it != shu.end(); it++)
    {
      ans *= pow((*it).second, (*it).first);
    }
    cout << ans << endl;
  }
}