Geek asks and answers

Divisible pairs in the range

I need help identifying a better approach to this problem (perhaps more mathematical!). Here are the details:

Description of the problem:

Given N and M, you need to find out how many pairs a, b (1 <b <= N) exist in such a way that (a + b) is divisible by M. For example, when N = 4 and M = 3, there are 2 possible pairs whose sum is divided by M and they are (1,2) and (2,4).

Limitations: 1 <= N <= 10 ^ 9 and 2 <= M <= 10 ^ 9. Time limit: 1 second

In my algorithm, I looped N times, making it O (N) algo. Here is the code:

#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;
}

I just check how many numbers are divisible by M in the range (2a, n + a), where 1 = <a <n. If you look at the sum of all (a, b) in the range, you will find out why I took (2a, n + a).

O (N) . N = 10 9 M = 2 249999999500000000 12 , . ? . , !

+3
2

.

:

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

, .

+3
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));
0

More articles:


All Articles