ICPC 7411 LCM Walk

acm math
  • LCM = A*B/gcd(A, B)
  • gcd 在前進後退時不會變.
    • let x = ab, y = bc , we can let every two integer in this form (3, 2) = (1 x 3, 1 x 2)
    • LCM = abc
    • abc + ab = a b (c+1)
    • gcd(a * b * (c+1), bc) = b = gcd(x, y), c and c+1 must be coprime
  • a2 = a1( (b/gcd) + 1 )
    • 因為gcd不變, gcd(b, a1) == gcd(b, a2)
    • 而a2, b 是己知的, 我們可求出a1

我們就不停往回dfs, 但要小心 gcd 最終會成為 1,
那gcd不變的那一條式就會不適用, 所以要檢查gcd有沒有變.

我們也可以先兩邊除去gcd, 那他們gcd就會成為1, 不用特別檢查.

icpc7411.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <cstdio>

int gcd(int a, int b) {
    if(b > a) return gcd(b, a);
    if(b == 0) return a;
    return gcd(b, a%b);
}

int solve(int ex, int ey, int gcr) {
    if(ex < 1 || ey < 1 || gcd(ex, ey) != gcr) return 0;
    int vl = 0, vr = 0;
    int dx = ey/gcr+1;
    int dy = ex/gcr+1;

    if(ey%dy == 0)
        vl = solve(ex, ey/dy, gcr);
    if(ex%dx == 0)
        vr = solve(ex/dx, ey, gcr);

    return vl+vr+1;
}

int main() {
    // freopen("input.txt", "r", stdin);
    int t, ex, ey;
    scanf("%d", &t);
    for(int nt = 1; nt <= t; ++nt) {

        scanf("%d%d", &ex, &ey);
        int gcr = gcd(ex, ey);
        printf("Case #%d: %d\n", nt, solve(ex, ey, gcr));
    }
    return 0;
}