LT19-Editorial

editorial
, ,
1

Problem Link

Loop Through

Author: isag2008

Difficulty

MEDIUM HARD

Prerequisites

Basic Hashing

Problem Statement

The doctor was about to embark on a journey back to the 80s to destroy the energy core of a device that is capable to warp dimensions, when TARDIS fails to work because of the effect of this device called Reality Disruptor, he's forced to set the coordinates of the place manually. Rose wishes to go with the doctor and so the doctor asks Rose to solve a puzzle, the answer to which gives the coordinates for the place.

He gives her two numbers N and P. She has to find the total number of pairs of natural numbers (first is lesser than the second) so that their sum is divisible by P, which is the coordinates.

Approach

To solve the problem in O(P) time limit, we can create array rem[P]. The array rem[i] will store the number of integers in the set A, such that on dividing by P, you get i as the remainder. rem[i] can be calculated in O(1) time. 
rem[i] = (N-i)/P;

Now, the sum of two integers is divisible by P if:

  • Both numbers are divisible by P and such selection can be made in rem [0]](rem[0]-1)/2 ways.
  • On dividing the first number by P, remainder is x then on dividing second number P, remainder must be (P-x). i.e. the number of ways can be rem[x]*rem[P-x] where x can belong to 0 to P/2.
  • P is even and on dividing both numbers, the reminder is P/2 i.e. rem[P/2]*(rem[P/2]-1)/2.

We can sum up all these possibilities to get the required output.

Solution

 #include<bits/stdc++.h>
 using namespace std;
 #define print(p) cout<<p<<endl;
 int main()
 {
     int T;
     long long int N, P, i;
     cin>>T;
     while(T--)
     {
         cin>>N>>P;
         long long int arr[P];
         arr[0] = N/P;
         for(i=1 ; i< P ; i++)
             arr[i] = (int)(N-i)/P + 1;
         if(K%2!=0)
         {
             long long int sum = 0;
             sum  = sum + (arr[0]*(arr[0] - 1))/2;
             for(i=1 ; i< (float)K/2 ; i++)
             {
                  sum = sum + arr[i]*arr[P-i];
             }
             cout<<sum<<endl;
         }
         else
         {
             long long int sum = 0;
             sum  = sum + (arr[0]*(arr[0] - 1))/2;
             for(i=1 ; i< K/2 ; i++)
             {
                  sum = sum + arr[i]*arr[K-i];
             }
             sum = sum + (arr[K/2]*(arr[K/2] - 1))/2;
             cout<<sum<<endl;
         }
     }
     return 0;
 }