You are given 3 numbers \(a, b\) and \(x\). You need to output the multiple of \(x\) which is closest to \(a^b\). If more than one answer exists, display the smallest one.
Input Format
The first line contains \(T\), the number of testcases.
\(T\) lines follow, each line contains 3 space separated integers (\(a, b\) and \(x\) respectively)
Constraints
\(1\leq T\leq 10^5\)
\(1\leq x\leq 10^9\)
\(0<a^b\leq 10^9\)
\(1\leq a\leq 10^9\)
\(-10^9\leq b\leq 10^9\)
Output Format
For each test case, output the multiple of x which is closest to \(a^b\)
Sample Input
3
349 1 4
395 1 7
4 -2 2
Sample Output
348
392
0
Explanationy
The closest multiple of 4 to 349 is 348.
The closest multiple of 7 to 395 is 392.
The closest multiple of 2 to 1/16 is 0.
Solution
The numbers we get stay in the following relationship with eachother, using a multiplier \(m\in\mathbb{N}\):
\[\begin{array}{rrl} & mx&=a^b\\ \Leftrightarrow & m&=\frac{a^b}{x}\\ \Leftrightarrow & m&=\exp(b\log(a)-\log(x)) \end{array}\]
Knowing the multiplier almost solves the problem. We now need to round the result to find the closest integer as a valid multiple. This also solves the problem that the smaller one must be chosen, if multiple possible solutions are there:
\[m = \left[\exp(b\log(a)-\log(x))\right]\]
In order to find the final multiple, we need to multply the multiplier \(m\) with the base \(x\), which results in the following C++ code:
#include <iostream>
#include <cmath>
int main() {
std::cout.precision( 10 );
int T;
std::cin >> T;
for (int i = 0; i < T; i++) {
double a, b, x;
std::cin >> a >> b >> x;
std::cout << round(exp(b * log(a) - log(x))) * x << std::endl;
}
return 0;
}