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,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("%dn",ans);
    }
    return 0;
}

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