You are given an integer NN. You have to count the number of distinct tuples (A,B,C,D)(A,B,C,D) with 1≤A,B,C,D≤N1≤A,B,C,D≤N such that A⋅B=C⋅DA⋅B=C⋅D. 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

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.

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.

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

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

Constraints

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

Counting Tuples solution codechef

 

3
3
50
35

Counting Tuples solution codechef

 

15
10950
4831

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 Comment