c - 无法理解竞争性考试？

Question

我参加了昨天举行的比赛。我无法解决下面的问题。比赛结束后我看到了一个人的解决方案，我无法理解。他是如何在这么短的时间内做到这一点的。他应用了什么。请解释他的解决方案。

You are given two numbers N and K and a set X.

X = { x : x is a natural number ≤ N } You have to find the total number of pairs of elements X[i] and X[j] belonging to the given set, such that, i < j and their sum is divisible by K.

Input Format:

An integer T followed by T lines, each containing a pair of space separated integers N and K.

Output Format:

T integers on separate lines. Each integer denotes the answer corresponding to that test case.

Constraints:

1≤T≤100

K≤N≤10^9

1≤K≤10000

Sample Input(Plaintext Link)

2
10 4
7 3

Sample Output(Plaintext Link)

10
7

Explanation

For the 1st test case, there are 10 pairs whose sum is divisible by 4. (1,3), (1,7), (2,6), (2,10), (3,5), (3,9), (4,8), (5,7), (6,10) and (7,9)

For the 2nd test case, there are 7 pairs whose sum is divisible by 3. (1,2), (1,5), (2,4), (2,7), (3,6), (4,5) and (5,7)

解决方案--

#include<stdio.h>

int main()
{
    long long int t,n,m,x,y,c=0;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld %lld",&n,&m);
        c=0;
        x=n/m;
        y=n%m;
            c+=((x*x*(m-1)-((m%2==0)?x:0))+x*(x-1))/2+y*x;
            if(y>m/2)
            c+=y-m/2;
        printf("%lld\n",c);
    }
}

Answer 1

提示

暴力方法:

您可以在 0<i<N 上编写双循环和i<j≤N并计算这些对，使得 (i + j) % K == 0 .

更明智的方法:

对于给定的i ，数量j这样(i + j) % K == 0大约等于(N - i) / K ，如每个 K第一个数字是 K 的倍数。 (您可以将近似值细化为精确表达式。)

更聪明的方法:

使用之前的结果，您需要对 (N - i)/K 求和为所有人贡献i 。此表达式对于 K 保持不变i 的连续值并从 i=1 开始减少(即 ~N/K )到 i=N (即 0 )，步长为 1 。所以总计数将类似于 K.T(N/K) ，其中T(m)表示m第一个三角形数，m.(m+1)/2 .

(同样，您可以将近似值细化为精确值并找到封闭公式。)

示例:

N=9, K=3

1 => *2*  3   4  *5*  6   7  *8*  9  => 3
2 =>      3  *4*  5   6  *7*  8   9  => 2
3 =>          4   5  *6*  7   8  *9* => 2
4 =>             *5*  6   7  *8*  9  => 2
5 =>                  6  *7*  8   9  => 1
6 =>                      7   8  *9* => 1
7 =>                         *8*  9  => 1
8 =>                              9  => 0