HackerRank Number Theory – Help Mike

Challenge: Help Mike

Subdomeniu: Number Theory (number-theory)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464729168

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/help-mike/problem

Cerinta

Harvey Specter has agreed to take Mike Ross to a meeting filled with brilliant scientists at NSA Headquarters. But, as always, it's not going to be easy for Mike. He has to solve a puzzle given by Harvey. 

Harvey gives two numbers N and K and defines a set A.<br>

*A = { x : x is a [natural number](https://en.wikipedia.org/wiki/Natural_number) ≤ N }*  
(i.e), A = {1,2,3,4,5,6,...., N}   

Mike has to find the total number of pairs of elements A[i] and A[j] belonging to the given set, such that, i < j and their sum is divisible by K<br>

**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<sup>9</sup>    
1<=K<=10000  

**Sample Input**  

    2
    10 4
    7 3

**Sample Output**

    10
    7

**Explanation**  

For the 1<sup>st</sup> 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 2<sup>nd</sup> 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)

Cod sursa

#!/bin/python3

import math
import os
import random
import re
import sys

def solve(n, k):
    max_sum = n + (n - 1)
    i_le_n = n // k
    max_no = max_sum // k 

    if k % 2 == 0:
        num1 = 0.25 * (i_le_n + 1) * i_le_n * k - i_le_n
        num2 = 0.25 * ((max_no + 1) * max_no - (i_le_n + 1) * i_le_n) * k
        num2 = n * (max_no - i_le_n) - num2
    else:
        num1 = 0.25 * (i_le_n + 1) * i_le_n * k - i_le_n + 0.25 * i_le_n
        num2 = 0.25 * ((max_no + 1) * max_no - (i_le_n + 1) * i_le_n) * k
        num2 = n * (max_no - i_le_n) - num2 + 0.25 * (max_no - i_le_n)

    print(num1, num2)
    return round(num1 + num2)
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        first_multiple_input = input().rstrip().split()

        n = int(first_multiple_input[0])

        k = int(first_multiple_input[1])

        result = solve(n, k)

        fptr.write(str(result) + '\n')

    fptr.close()