图片说明

  • 题意：
  • 给出一个数n<=1e18,问你将其分解成整数的唯一分解定理后对应的质数次幂的最大值。
  • 题解：
  • 这题数据真的非常狗血。
  • 先用正常的中国剩余定理求出来前10001项的次幂，然后分类讨论，
  • 如果n的四分之一次方是整数，更新最大值4
  • 如果n的三分之一次方是整数，更新最大值3，这里不能直接用pow，应该用二分，精度问题
  • 如果n的二分之一次方是整数，更新最大值2，
  • 如果都不行，更新最大值1
  • 代码：
    #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 10010;
ll a[maxx+10];
bool pri[maxx+10];
int cnt = 0;
bool is_prime(ll x)
{
  for(int i=0;i<cnt&&(ll)a[i]*a[i] <= x;i++){
      if(x % a[i] == 0)
          return 0;
  }
  return 1;
}
void prime()
{
  for(int i=2;i<=maxx;i++){
      if(!pri[i])
          a[cnt++] = i;
      for(int j=0;(j<cnt && (ll)i*a[j]<=maxx);j++){
          pri[i*a[j]] = 1;
          if(i%a[j] == 0)
              break;
      }
  }
}
bool check(ll x)
{
  ll l = 10010,r = 1000000;
  while(l <= r)
  {
      ll mid = (l+r)>>1;
      ll k = mid*mid*mid;
      if(k > x){
          r = mid-1;
      }
      else if(k < x){
          l = mid+1;
      }
      else{
          return true;
      }
  }
  return false;
}
int main()
{
  prime();
  int t,ans = 1<<15;
  ll n;
  scanf("%d",&t);
  while(t--)
  {
      ans = 1<<15;
      scanf("%lld",&n);
      for(int i=0;i<cnt;i++)
      {
          int k=0;
          if(n%a[i] == 0)
          {
              while(n%a[i] == 0){
                  n /= a[i];
                  k++;
              }
              ans = min(ans,k);
          }
          if(n == 1)
              break;
      }
      if(n > 10009)
      {
          ll k1 = (ll)sqrt(sqrt(n));
          ll k2 = (ll)sqrt(n);
          if(k1*k1*k1*k1 == n){
              ans = min(ans,4);
          }
          else if(k2*k2 == n){
              ans = min(ans,2);
          }
          else if(check(n)){
              ans = min(ans,3);
          }else{
              ans = 1;
          }
      }
      printf("%d\n",ans);
  }
  return 0;
}