Counting Tuples solution codechef

Counting Tuples solution codechef

You are given an integer NN. You have to count the number of distinct tuples (A,B,C,D)(A,B,C,D) with 1A,B,C,DN1≤A,B,C,D≤N such that AB=CDA⋅B=C⋅D.

Counting Tuples solution codechef

Two tuples, say (A,B,C,D)(A,B,C,D) and (E,F,G,H)(E,F,G,H) are considered to be different if at least one of the following conditions hold true:

  • AEA≠E
  • BFB≠F
  • CGC≠G
  • DHD≠H.

Input Format Counting Tuples solution codechef

  • First line will contain TT, number of testcases. Then the testcases follow.
  • Each testcase contains a single integer on a new line – NN, as described in the problem statement

Output Format Counting Tuples solution codechef

For each testcase, output the answer on a new line – the number of tuples as described in the problem statement.

Constraints Counting Tuples solution codechef

  • 1T101≤T≤10
  • 1N1061≤N≤106

Sample Input 1 Counting Tuples solution codechef

3
3
50
35

Sample Output 1 Counting Tuples solution codechef

15
10950
4831

Explanation Counting Tuples solution codechef

Test case 11: Following tuples satisfy the given condition:

  • (1, 1, 1, 1)
  • (1, 2, 2, 1)
  • (1, 3, 3, 1)
  • (2, 1, 1, 2)
  • (2, 2, 2, 2)
  • (2, 3, 3, 2)
  • (3, 1, 1, 3)
  • (3, 2, 2, 3)
  • (3, 3, 3, 3)
  • (1, 2, 1, 2)
  • (2, 1, 2, 1)
  • (1, 3, 1, 3)
  • (3, 1, 3, 1)
  • (2, 3, 2, 3)
  • (3, 2, 3, 2)

AB=CDA⋅B=C⋅D holds true for all these tuples.

Leave a Reply

Your email address will not be published. Required fields are marked *

*