题意:
牛妹手里捧着 T 个数,对于每个数x,将其分解质因数,并输出它的质因子指数的最小值。
形式化地,对于数x = p1^a1 * p2^a2 … pk^ak,输出min{a1,a2…ak}。
1<=T<=100000 , 1<=n<=1018
题解:
首先想到素数的话min=1 米勒罗宾素数检测(Miller-Rabin)
然后min<=64
然后指数<=sqrt(1e18)
然后假设min==6就可以小范围素数筛搞搞
T=1e5
所以把1e4内的质数筛出来, 每次先把 $n$, 变成 $1$ 或者 $>1e4$ 的数
对于剩下的数大于 $1e4$ 的剩下的答案无非是 1,2,3,4
#include <bits/stdc++.h> using namespace std; #define int long long const int N=2e5+5; bool vis[N]; int prime[N]; int tot=0; void prim() { vis[1]=1; for(int i=2; i<=10005; i++) { if(!vis[i]) prime[++tot]=i; for(int j=1; j<=tot; j++) { if(i*prime[j]>10000) break; vis[i*prime[j]]=1; if(i%prime[j]==0) break; } } } signed main() { prim(); int t; cin>>t; while(t--) { int n; cin>>n; if(n==1) { cout<<0<<endl; continue; } int ans=1e18; for(int i=1; i<=tot; i++) { int cnt=0; while(n%prime[i]==0) { n/=prime[i]; cnt++; } if(cnt) ans=min(ans, cnt); } if(n>10000) { int a=sqrt(1.0*n); int c=(pow(n*1.0, 1.0/3)+0.1); int b=sqrt(a); if(b*b*b*b==n) ans=min(ans, 4ll); else if(c*c*c==n) ans=min(ans, 3ll); else if(a*a==n) ans=min(ans, 2ll); else ans=min(ans, 1ll); } cout<<ans<<endl; } return 0; }
|
总结
提示:这里对文章进行总结:
例如:以上就是今天要讲的内容,本文仅仅简单介绍了pandas的使用,而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。