CF102780D Power play【数学】【二分】【快速幂】

Description

While analyzing a mathematical problem, a programmer, Basil by name, noticed an interesting fact: for the numbers $2$ and $4$ holds the equality $2^4=4^2$. ‘This could be a great challenge for the participants of the programming championship,’ he thought. Unfortunately, Basil could not find other such pairs of numbers, the pair $2$ and $4$ was his only combination that he could think of. ‘Okay, then we’ll change the conditions, let there be three numbers,’ Basil decided. The written program of enumeration options confirmed that with three numbers the task made sense.

Your task: find the integer $x$ by the given integers $a$ and $b$ such that falls in the range from $1$ to $10^{18}$ (Basil’s program didn’t deal with greater numbers) such that $a^x=x^b$. If there are several such numbers, type the smaller of them. If such a number does not exist, type $0$.

Input

The input data consist of two integers $a$ and $b (2\le a,b\le 10000; a\ne b)$, separated by a blank space.

Output

The integer $x$ if there is a solution, or $0$ (zero) if there is no solution.

题解

\begin{aligned} &a^x&=x^b\ &x\ln a&=b\ln x\ &\frac{x}{\ln x}&=\frac{b}{\ln a} \end{aligned}

Code：

#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<bitset>
using namespace std;
#define ls (k<<1)
#define rs (k<<1|1)
//#define mid ((l+r)>>1)
#define ll long long
#define eps 1e-7
int gcd(int x,int y)
{
while(y)
{
int t=x%y;
x=y;
y=t;
}
return x;
}
int cnt[1010];
char s[10010];
const ll p=1000000007;
ll qpow(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
ans=ans*x%p;
x=x*x%p;
y>>=1;
}
return ans;
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
if((1ll<<b)==1ll*a*a)
{
puts("2");
return 0;
}
double t=b/log(a);
double l=exp(1),r=1e18;
while(r-l>1e-8)
{
double mid=(l+r)/2;
double tt=mid/log(mid);
if(tt<t)
l=mid;
else
r=mid;
}
ll i=floor(l+.5);
if(qpow(a,i)==qpow(i,b))
printf("%lld\n",i);
else
puts("0");
return 0;
}



Subscribe

/* */