3

我需要帮助找出解决这个问题的更好方法（可能是一个更数学的方法！）。以下是详细信息：

问题陈述：

给定 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 9和 M=2，程序在 12 秒内将答案打印为 249999999500000000，这非常慢。还可以使用哪些其他方法？我想不出更好的方法。请帮忙！

4

2 回答 2

3

您可以简单地计算，而不是测试。

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

(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, ...)？

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

于 2012-05-11T06:46:03.233 回答
0 
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));
于 2012-05-11T11:41:05.043 回答