[2019杭电多校第四场][hdu6623]Minimal Power of Prime

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6623

题目大意为求一个数的唯一分解的最小幂次。即120=2³*3¹*5¹则答案为1。

因为数字太大不能直接分解，所以可以先分解1e4内的素因子，这样所有幂次可能>=5的数都被分解了，然后判断剩余的数是否是一个数的4次方如果是的话ans=min（ans，4），

如果不是的话再判断是不是一个数的3次方，如果是的话ans=min（ans，3）。

如果不是的话就判断是不是一个数的平方，如果是ans=min（ans，2），如果不是那么ans=1。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn = ;

 int a[], tot;

 ll b[];

 void init() {

     tot = ;

     for (int i = ; i <= ; i++)

         if (a[i] == ) {

             b[tot++] = (ll)i;

             for (int j = i * ; j <= ; j += i)

                 a[j] = ;

         }

 }

 int check(ll n) {

     ll l = , r = pow(n*1.0, 1.0 / ) + ;

     while (l <= r) {

         ll mid = (l + r) >> ;

         ll y = mid * mid*mid;

         if (y == n) return ;

         else if (y > n) r = mid - ;

         else l = mid + ;

     }

     return ;

 }

 int main() {

     init();

     int t;

     scanf("%d", &t);

     while (t--) {

         ll n;

         scanf("%lld", &n);

         int x, ans = ;

         for (int i = ; i < tot; i++) {

             if (n < b[i]) break;

             x = ;

             if (n%b[i] == ) {

                 while (n%b[i] == ) {

                     n /= b[i];

                     x++;

                 }

                 ans = min(ans, x);

             }

         }

         if (n ==  || ans == ) printf("%d\n", ans);

         else {

             ll m1 = (ll)sqrt(sqrt(n*1.0));

             ll m2 = (ll)sqrt(n*1.0);

             if ((m1*m1*m1*m1) == n) ans = min(ans, );

             else if (check(n) == ) ans = min(ans, );

             else if (m2*m2 == n) ans = min(ans, );

             else ans = ;

             printf("%d\n", ans);

         }

     }

     return ;

 }

[2019杭电多校第四场][hdu6623]Minimal Power of Prime的相关教程结束。