c - 范围内的可分对

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 < n。如果您查看范围内所有 (a,b) 的总和，您就会知道我为什么取 (2a,n+a)。

但是这种O(N) 方法不是很快。对于 N=10⁹ 和 M=2，程序在 12 秒内将答案打印为 249999999500000000，这非常慢。还可以使用哪些其他方法？我想不出任何更好的方法。请帮忙!

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，每对 (a, b)与 1 <= a < b <= N这样 a+b % M == 0必须具有以下形式:

(i+1, N - d*M - (N+1)%M - i)对于 0 <= d和 0 <= i

现在你必须回答以下两个问题:

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

一旦你发现了，你应该能够想出一个公式来确定恒定时间内有效对的数量。