首页 > 代码库 > UVA - 113 Power of Cryptography (大数幂+二分)
UVA - 113 Power of Cryptography (大数幂+二分)
打开链接
给定n和p,找出 k使得 k^n==p 。1<=k<=10^9
我们可以二分k,用高精度表示出k^n 然后跟p比较。
#include<cstdio> #include<cmath> #include<cstring> const int maxn = 1000000000; struct bign { int len; int f[1500]; bign() {memset(f,0,sizeof(f)); len=0;} }; int n,ans; char p[150]; bign mul(bign a,bign b) //大数相乘 { bign c; for(int i=0;i<a.len;i++) { for(int j=0;j<b.len;j++) { c.f[i+j]=a.f[i]*b.f[j]+c.f[i+j]; c.f[i+j+1]=c.f[i+j]/10+c.f[i+j+1]; c.f[i+j]=c.f[i+j]%10; } } int l=a.len+b.len; while(!c.f[l]) l--; c.len=l+1; return c; } bign solve(int x) //大数幂 返回 a的x次幂 { bign a,b; int l=0; while(x>0) { a.f[l]=b.f[l]=x%10; x/=10; l++; } a.len=b.len=l; for(int i=1;i<n;i++) { a=mul(a,b); } return a; } int compare(bign a) //比较 大数与字符串比较 { int l=strlen(p),flag=0; if(a.len<l) return 1; else if(a.len>l) return -1; else { for(int i=0;i<l;i++) { if(a.f[a.len-1]<p[i]-'0') {flag=1;break;} else if(a.f[a.len-1]>p[i]-'0') {flag=-1;break;} else {a.len--;} } return flag; } } void binary(int x,int y) //在 x 和 y之间二分 k { bign a; while(x<=y) { int mid=(x+y)/2; a=solve(mid); int t=compare(a); if(t==0) { ans=mid; return; } else if(t==1) x=mid+1; else y=mid-1; } } int main() { //freopen("a.txt","r",stdin); while(~scanf("%d",&n)) { getchar; scanf("%s",p); binary(1,maxn); printf("%d\n",ans); } return 0; }
当然更快的方法是直接 用double求。
#include<cstdio> #include<cmath> int main() { double n,p; while(~scanf("%lf%lf",&n,&p)) { printf("%.0lf\n",pow(p,1.0/n)); } return 0; }
UVA - 113 Power of Cryptography (大数幂+二分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。