java - Combitronics和质因数分解:计算(m，n)对的数量，其中GCD(m，n)= x

计算（m，n）对的个数，其中GCD（m，n）=x，比如x=1和
1<=m<=m=10^5和1<=n<=n=10^5。
将给出M和N
我知道我们可以使用（蛮力）2个迭代器来遍历m和n，并检查gcd是否等于1，从而增加可能的对数。
但这只对较小的数字有效，而对较大的数字则需要大量的时间比如M=100000和N=100000
有一种方法我们可以用质因数来计算。
注意：我只想要可能的对的数量，而不是对。

最佳答案

让我们从你的蛮力算法开始：

for (n = 1; n <= N; n++) {
    for (m = 1; m <= M; m++) {
        if (gcd(m, n) == x) count++;
    }
}

当x大于1时，您可以加快此速度，因为如果n和m的gdc为x，则这些数字本身必须是x的倍数：

for (n = x; n <= N; n += x) {
    for (m = x; m <= M; m += x) {
        if (gcd(m, n) == x) count++;
    }
}

在这些循环中，我们可以将所有数字除以x：

int NN = N / x;
int MM = M / x;

for (n = 1; n <= NN; n++) {
    for (m = 1; m <= MM; m++) {
        if (gcd(m, n) == 1) count++;
    }
}

检查GDC为1是对互质对的测试。一点点的研究导致了Wikipedia并出现了一个生成所有互质对的简洁（并且有大量说明）算法：

#define NN (N / X)
#define MM (M / X)

void spread(int m, int n, int *count)
{
    if (n > NN) return;
    if (m > MM) return;

    if (n != m && m <= NN) (*count)++;
    (*count)++;

    spread(2*m - n, m, count);
    spread(2*m + n, m, count);
    spread(m + 2*n, n, count);
}

int main()
{
    int count = 1;

    spread(2, 1, &count);
    spread(3, 1, &count);

    printf("%d\n", count);

    return 0;
}

计数从1开始，因为成对生成器不生成（1，1），这也符合您的条件。如果M大于或等于N，则该代码有效。如果没有，就换掉它们。
这种自底向上的方法比循环快得多，就像对erathostenes的筛选比对一系列数字进行天真的素性检查快一样。
恐怕这是C，不是Javacount作为指针传递；我想java习惯用法可能是一个引用。当然，您也可以从spread返回计数并累积。（如果N、NN等不是全局的，那就太好了，但我相信您会在java中用一个漂亮、整洁的类来包装它。）
编辑：上面的代码是递归的，需要很大的堆栈空间如果线性化代码并使用队列，则可以将所需空间从堆栈迁移到堆代码如下所示：

int spread(m, n)
{
    Queue q;
    int count = 1;

    q.push(m, n);

    while (!q.empty()) {
        int m, n;

        q.pull(&m, &n);

        if (n <= NN && m <= MM) {
            if (n != m && m <= NN) count++;
            count++;

            q.push(2*m - n, m);
            q.push(2*m + n, m);
            q.push(m + 2*n, n);
        }
    }

    return count;
}

int main()
{
    Queue q;
    int count = 1;

    count += spread(2, 1);
    count += spread(3, 1);

    printf("%d\n", count);

    return 0;
}

如果您的M和N超过100000，则需要相当长的时间才能运行。但是你可以很容易地把它并行，因为（2，1）和（3，1）的情况是独立的。