简答题
偏难
#20241
最大因数 时间限制:1 s,内存限制:512 MB 【问题描述】 给定一棵有 10^9 个结点的有根树,这些结点依次以 1、2、……、10^9编号,根结点的编号…
最大因数
时间限制:1 s,内存限制:512 MB
【问题描述】
给定一棵有 10^9 个结点的有根树,这些结点依次以 1、2、……、10^9编号,根结点的编号为 1。
对于编号为 k(2 <= k <= 10^9)的结点,其父结点的编号为 k 的因数中除 k 以外最大的因数。
现在有 q 组询问,第 i(1<= i <= q)组询问给定 xi、yi,请你求出编号分别为 xi、yi 的两个结点在这棵树上的距离。
两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
【输入描述】
第一行,一个正整数 q,表示询问组数。
接下来 q 行,每行两个正整数 xi、yi,表示询问结点的编号。
【输出描述】
输出共 q 行,每行一个整数,表示结点 xi、yi 之间的距离。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于60%的测试点,保证 1 <= xi、yi <= 1000。
对于所有测试点,保证 1 <= q <= 1000,1 <= xi、yi <= 10^9。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50;
int a[N], cnta, b[N], cntb;
int f[N], t, q;
void factorize(int x, int a[], int &cnt) {
a[0] = x;
t = 0;
for (int i = 2; i * i <= x; i++)
while (x % i == 0) {
f[++t] = i;
x /= i;
}
if (x > 1)
f[++t] = x;
for (int i = 1; i <= t; i++)
a[i] = a[i - 1] / f[i];
cnt = t;
}
int main() {
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
factorize(x, a, cnta);
factorize(y, b, cntb);
int px = 0, py = 0;
while (a[px] != b[py]) {
if (a[px] > b[py])
px++;
else
py++;
}
cout << px + py << endl;
}
return 0;
}</pre>
这道题暂未补解析。