3

この問題に対するより良いアプローチを見つける手助けが必要です (もっと数学的なアプローチかもしれません!)。詳細は次のとおりです。

問題文：

N と M を指定すると、(a+b) が M で割り切れる a,b (1 <= a < b <=N) のペアがいくつあるかを調べる必要があります。たとえば、N=4 で M=3 の場合、合計が M で割り切れる 2 つの可能なペアがあり、それらは (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;
}

1 =< a < n の範囲 (2a,n+a) で、M で割り切れる数の数を確認しているだけです。範囲内のすべての(a,b)の合計を見ると、なぜ(2a,n+a)を取ったのかがわかります。

ただし、このO(N)アプローチはあまり高速ではありません。N=10 9および M=2 の場合、プログラムは答えを 249999999500000000 として 12 秒で出力しますが、これはかなり遅いです。他にどのようなアプローチを使用できますか? より良いアプローチは考えられません。助けてください！

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 で割り切れるようにするために、タプルの 2 番目の要素から減算する必要があります)

より一般的には、 0Nを超える場合、そのようなものとMのすべてのペアは、次の形式でなければなりません。(a, b)1 <= a < b <= Na+b % M == 0

(i+1, N - d*M - (N+1)%M - i)0 <= dと_0 <= i

ここで、次の 2 つの質問に答える必要があります。

  • の最大値は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 に答える