HDU 6623-Minimal Power of Prime【思维 枚举】
- 转载:www.GuoXiongfei.cn
- /
- 时间:2019-08-15 11:37:12
- /
- 浏览:93,942次
- /
- 分类:css , Javascript , Java , DataBase , app
题意:给你一个数n(n<1e18),问你质因数分解后最少的幂是多少,例如8=2*2*2,就是3.思路:先暴力打出来1e4的素数表,然后进行质因数分解,如果没有n分解后为1,或者最少幂次已经为1就说明答案为1,否则n只可能是某个素数的4次幂或者3次幂或者2次幂,或者n就是一个大素数。#include<bits/stdc .h>usingnamespacestd;typedeflo...
题意:给你一个数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;}
�
源文地址:https://www.guoxiongfei.cn/csdn/7530.html