4729: 【GESP2506六级】最⼤因数

#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;
}