范围内可被整除的数对

Question

我需要帮助想出一种更好的方法来解决这个问题（或许是一种更数学化的方法！）以下是详细信息：

问题陈述：

给定N和M，您需要找出有多少对a，b（1 <= a < b <= N）满足(a + b)可被M整除。例如当N=4且M=3时，有2组可能的对，它们的和可以被M整除，分别是(1,2)和(2,4)。

限制条件: 1 <= N <= 10^9，2 <= M <= 10^9。 时间限制：1秒

在我的算法中，我使用了循环N次，使其成为O(N)算法。以下是代码:

#include <stdio.h>
typedef unsigned long long ULL;
int main()
{
    int t,m,n,a; ULL ans=0;
    scanf("%d\n",&t);
    while(t--) // test cases
    {
            // Main logic
        scanf("%d %d",&n,&m);
        ans=0;
        for(a=1;a<n;a++)
            ans += (n+a)/m - (a*2)/m;
        printf("%llu\n",ans);
    }
    return 0;
}

我只是在检查范围（2a，n+a）内有多少个数字可被M整除，其中1≤a

然而，这种O（N）方法不太快。对于N=10的9次方和M=2，程序在12秒内将答案打印为249999999500000000，速度相当慢。还有哪些方法可以使用？我想不出更好的方法。请帮帮我！

- Rushil Paul

---

不是测试，而是生成它们：(M, 0), (M-1, 1), (M-2, 2)等，然后生成 (2M, 0), (2M-1, 1)等。 - Jerry Coffin

你的意思是走相反的路吗？也就是说，找出在范围[1,N]内落在M的倍数上的两个正整数的分割方式有多少种？那会更加困难和耗时。 - Rushil Paul

@Rushil 这更困难，但速度更快，看看 Philips 的回答。 - Gunther Piez

Answer 1

不需要测试，你可以直接计数。

让我们列出所有可能的配对：

(1, N - (N+1)%M),
(1, N - M - (N+1)%M),
(1, N - 2*M - (N+1)%M),
...
(2, N - (N+1)%M - 1),
(2, N - M - (N+1)%M - 1),
(2, N - 2*M - (N+1)%M - 1),
...

我们需要从元组的第二个元素中减去 (N+1)%M，以使元素的和可被 M 整除。

更一般地，给定 N 和 M > 0，对于每一对满足 1 <= a < b <= N 且 a+b % M == 0 的二元组 (a, b)，必须具有以下形式： (i+1, N - d*M - (N+1)%M - i)，其中 0 <= d 且 0 <= i 现在你需要回答以下两个问题：

• i 的最大值是多少？
• 对于每个有效的 i，d 的最大值是多少，即存在多少对 (i+1, ...)？

一旦你找到答案，就应该能够提出一个公式在常数时间内确定有效对数。

- Philip

---

你的意思是 N+1%M 还是 (N+1)%M？因为 1%M 总是等于1。 - Rushil Paul

好吧，我想我得运行一个循环。但它肯定比我的以前的程序快...在最坏的情况下，循环将运行N/2次。 - Rushil Paul

Answer 2

ans = n / m * (n - 1)
    + (n / m) * (n / m - 1) / 2 * m
    + (n % m + m / 2) / m * (n - m + n % m)
    + (n - m + n % m) % m * (n / m)
    - (n / m) * (n / m - 1) * m
    - (m / 2) * (n / m)
    - (n % m) * (n / m * 2)
    - (n % m / ((m + 1) / 2)) * (n % m % ((m + 1) / 2));

- Ivarpoiss

---

回到Fortran77几乎完成。 - Michael Dorgan