LAOI R1-A

sto_5k_orz · 2023-07-15 15:07:04 · 题解

官方题解

首先，令 g=\gcd(i,j)。

那么 i 到 g 有 i-g 的边，j 到 g 也有一条 j-g 的边。

那么 i+j-2g 是其中一种方案。

此外，按照 \gcd 的定义，如果 i 到更小的公约数 g',g'<g，那么 i+j-2g'>i+j-2g，更加不优。

所以答案是 i+j-2g。

当然也可能是 2\operatorname{lcm}(i,j)-i-j，但是这样一定不优。

证明：

不妨设 i\le j。

令 g=\gcd(i,j),l=\operatorname{lcm}(i,j)。

又因为 ij=gl，并且 l\ge j,g\le i。

又因为两个数积相等，差越大和越大，所以上式成立。

考虑 \forall i,j\ge 0,j\ge i, i+j\ge 2\sqrt {ij}，所以两个数积相等，j-i 越小，i+j 越大。

所以 i+j\le l+g。

#include<bits/stdc++.h>
using namespace std;
#define gc getchar
#define pc putchar
#define W while
#define I inline
namespace SlowIO{
    I int read() {
        int x = 0, f = 1; char ch = gc();
        W(ch < '0' || ch > '9') {if(ch == '-') f = -f; ch = gc();}
        W(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
        return x * f;
    }
    I void Read(int &x) {x = read();}
    I void Read(int &x, int &y) {Read(x), Read(y);}
    I void write(int x) {
        if(x < 0) pc('-'), x = -x;
        if(x > 9) write(x / 10);
        pc(x % 10 + '0');
    }
    I void writeln(int x) {write(x); pc('\n');}
} using namespace SlowIO;
signed main() {
    int t; Read(t);
    while(t--) {
        int n, q; Read(n, q); 
        while(q--) {
            int a, b; Read(a, b); int g = __gcd(a, b);
            writeln(a + b - 2 * g);
        }
    }
    return 0;
}