简答题 偏难
#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】

3
1 3
2 5
4 8

【样例输出1】

1
2
1

【样例输入2】

1
120 650

【样例输出2】

9

【数据范围】

对于60%的测试点,保证 1 <= xi、yi <= 1000。

对于所有测试点,保证 1 <= q <= 1000,1 <= xi、yi <= 10^9。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;algorithm&gt; 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 &amp;cnt) {     a[0] = x;     t = 0;     for (int i = 2; i * i &lt;= x; i++)         while (x % i == 0) {             f[++t] = i;             x /= i;         }     if (x &gt; 1)         f[++t] = x;     for (int i = 1; i &lt;= t; i++)         a[i] = a[i - 1] / f[i];     cnt = t; } int main() {     cin &gt;&gt; q;     while (q--) {         int x, y;         cin &gt;&gt; x &gt;&gt; y;         factorize(x, a, cnta);         factorize(y, b, cntb);         int px = 0, py = 0;         while (a[px] != b[py]) {             if (a[px] &gt; b[py])                 px++;             else                 py++;         }         cout &lt;&lt; px + py &lt;&lt; endl;     }     return 0; }</pre>
这道题暂未补解析。