【题目大意】在一棵树上，每个节点的祖先被定义为该节点自身以外的最大因数，现需求解树上任意两点之间的距离。 根据数据范围要求，最大因数不包含此数，最小因数不包含1。

【考纲知识点】数学知识

【解题思路】从小到大找到所有的因数，然后从x起，x除以最小的因数得到了x的父亲节点x’“除x本身外最大的因数”，然后x’再除以第二小的因数得到x’的父亲节点。在此期间，统计因数的个数，相加即可得到结果。注意是多组测试数据。

参考程序
 

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 50;

int q;
int a[N], cnta;
int b[N], cntb;
int f[N], t;

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() {
    scanf("%d", &q);
    while (q--) {
        int x, y;
        scanf("%d%d", &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++;
        }
        printf("%d\n", px + py);
    }
    return 0;
}