UVA - 113 Power of Cryptography （大数幂+二分）

打开链接

给定n和p，找出 k使得 k^n==p 。1<=k<=10^9

我们可以二分k，用高精度表示出k^n 然后跟p比较。

?

#include
  
   
#include
   
     #include
    
      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
     
      0) { a.f[l]=b.f[l]=x%10; x/=10; l++; } a.len=b.len=l; for(int i=1;i
      
       l) return -1; else { for(int i=0;i
       
        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; } 
       
      
     
    
   
  

?

?

#include
  
   
#include
   
     int main() { double n,p; while(~scanf("%lf%lf",&n,&p)) { printf("%.0lf\n",pow(p,1.0/n)); } return 0; }
   
  

?

?