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