给你两个整数 x, y. 需要你求出两个数 a, b. 满足对 x 乘 a 次 b 等于 y (即 x * ba = y).
例如 x=4, y=100时, 存在 a=2, b=5. 使等式成立.
输入格式
第一行包含一个整数 t (1 ≤ t ≤ 104）表示测试用例的数量。
每个测试用例由一行包含两个整数 x 和 y (1≤ x，y ≤ 100).
输出格式
如果可以选择一对正整数 a 和 b 使得 x 等于 y 在上述过程之后，打印这两个整数。您打印的整数应不小于 1 并且不大于 109（可以证明，如果答案存在，则存在一对整数 a 和 b 满足这些约束）。如果有多个这样的数对，请输出其中任何一个。
如果无法选择一对整数 a 和 b 使得 x 等于 y，则输出整数 0 两次。
输入样例 复制
3
3 75
100 100
42 13
输出样例 复制
2 5
3 1
0 0
#include <stdio.h>
#include <math.h>
void find_a_b(int x, int y, int *a, int *b)
{
*a = 0;
*b = 0;
if (y % x != 0) {
// 如果y不能被x整除，则不存在满足条件的a和b
return;
}
int i, j;
double logyx, logx, logb;
for (i = 2; i <= y; i++) {
// b从2开始尝试，x的0次方是1，所以也需要包括1
for (j = 0; ; j++) {
logyx = log(y) / log(i + j);
logx = log(x) / log(i + j);
logb = fmod(logyx, logx);
if (fabs(logb) < 1e-9) {
// 找到了满足条件的b值
*a = (int)(logyx / logx);
*b = i + j;
return;
} else if (logb < 0) {
// 如果b太大，就不必再尝试了
break;
}
}
}
}
int main()
{
int t, x, y, a, b;
scanf("%d", &t);
while (t--) {
// 读取输入数据
scanf("%d%d", &x, &y);
// 找到满足条件的a和b
find_a_b(x, y, &a, &b);
// 打印结果
printf("%d %d\n", a, b);
}
return 0;
}
解题思路：
假设有方程
$$
a\times b ^ m = y
$$
因为 $a$ 与 $y$ 同乘以一个常数后结果不变，所以先令 $b=1$，$a=y$ 可得
$$
a=y,b=1,m=0
$$
显然这是一组解，并且是唯一的满足这个条件的解（因为 $m$ 不可能为负）。如果 $y$ 不能被 $x$ 整除，那么直接输出 0。
接下来我们从 $m=1$ 开始枚举 $m$，每次求出对应的 $b$，如果 $b$ 是整数，那么就是一组合法解，此时输出 $a$ 和 $b$ 即可。
判断数字是否为整数可以使用 math.isqrt() 函数，判断该数字的平方根是否为整数。
下面是C语言的实现：
#include<stdio.h>
#include<math.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int x,y;
scanf("%d%d",&x,&y);
int flag=0;
for(int i=1;i<=sqrt(y);i++)
{
int b=i,a=1;
while(y%pow(x,a)==0)
{
a++;
}
if(pow(x,a-1)==pow(y,1.0/b))
{
printf("%d %d\n",a-1,b);
flag=1;
break;
}
}
if(!flag) printf("0 0\n");
}
return 0;
}
解释一下其中的思路：
for 循环中，枚举 b 并依次判断；while 循环中，对 a 进行累加，直到不满足条件 $x^a=y^b$ 为止；for 循环结束后还没有找到符合条件的值，则输出 0 0。这种解法的时间复杂度是 O(T sqrt(Y) log(Y))，其中 T 是测试用例的数量。