HDU 6623-Minimal Power of Prime【思维 枚举】

题意：给你一个数n（n< 1e18）,问你质因数分解后最少的幂是多少，例如8=2*2*2，就是3.

思路：先暴力打出来1e4的素数表，然后进行质因数分解，如果没有n分解后为1,或者最少幂次已经为1就说明答案为1，否则n只可能是某个素数的4次幂或者3次幂或者2次幂，或者n就是一个大素数。

#include<bits/stdc  .h>using namespace std;typedef long long ll;#define lson l, mid, rt << 1#define rson mid1, r, rt << 1|1const int maxn = 1e410;const int inf = 0x3f3f3f3f;int a[maxn], prime[maxn];ll n;void init(){ for(int i = 2; i < maxn;i) {  if(!a[i])  {prime[  prime[0]] = i;for(int j = i * 2; j < maxn; j  = i) a[j] = 1;  } }}bool check(ll x, int y){ ll res1 = 1, res2 = 1, res3 = 1; //开根号会有偏差 for(int i = 1; i <= y;i) {  res1 *= x;  res2 *= (x1);  res3 *= (x - 1); } if(res1 == n || res2 == n || res3 == n)  return true; return false;}int main(){ init(); int t; scanf("%d", &t); while(t--) {  scanf("%lld", &n);  ll tmp = n;  int ans = inf;  for(int i = 1; i <= prime[0];i)  {if(tmp % prime[i] == 0 && tmp){ int cnt = 0; while(tmp % prime[i] == 0) { cnt;  tmp /= prime[i]; } ans = min(ans, cnt);}  }  if(tmp == 1 || ans == 1)  {printf("%d\n", ans);continue;  }  ll x = pow(n, 1.0/4);  if(check(x, 4))ans = min(ans, 4);  else if(check(pow(n, 1.0/3), 3))ans = min(ans, 3);  else if(check(pow(n, 1.0/2), 2))ans = min(ans, 2);  elseans = min(ans, 1);  printf("%d\n", ans); } return 0;}

�