August Long Challenge Special Triplets Solution

Page Contents

Special Triplets Solution

Gintoki has been very lazy recently and he hasn’t made enough money to pay the rent this month. So the old landlady has given him a problem to solve instead, if he can solve this problem the rent will be waived. The problem is as follows:

Also See: August Long Challenge 2021 Solutions

A triplet of integers (A,B,C)(A,B,C) is considered to be special if it satisfies the following properties for a given integer NN :

AmodB=CAmodB=C
BmodC=0BmodC=0
1≤A,B,C≤N1≤A,B,C≤N

Example: There are three special triplets for N=3N=3.

(1,3,1)(1,3,1) is a special triplet, since (1mod3)=1(1mod3)=1 and (3mod1)=0(3mod1)=0.
(1,2,1)(1,2,1) is a special triplet, since (1mod2)=1(1mod2)=1 and (2mod1)=0(2mod1)=0.
(3,2,1)(3,2,1) is a special triplet, since (3mod2)=1(3mod2)=1 and (2mod1)=0(2mod1)=0.

The landlady gives Gintoki an integer NN. Now Gintoki needs to find the number of special triplets. Can you help him to find the answer?

Input Format

The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
The first and only line of each test case contains a single integer NN.

Output Format

For each testcase, output in a single line the number of special triplets.

Constraints

1≤T≤101≤T≤10
2≤N≤1052≤N≤105

Subtasks

Subtask #1 (5 points): 2≤N≤1032≤N≤103

Subtask #2 (20 points): 2≤N≤1042≤N≤104

Subtask #3 (75 points): Original constraints

Sample Input 1

Sample Output 1

3
6
9

Explanation

Test case 11: It is explained in the problem statement.

Test case 22: The special triplets are (1,3,1)(1,3,1), (1,2,1)(1,2,1), (3,2,1)(3,2,1), (1,4,1)(1,4,1), (4,3,1)(4,3,1), (2,4,2)(2,4,2). Hence the answer is 66.

Test case 33: The special triplets are (1,3,1)(1,3,1), (1,2,1)(1,2,1), (3,2,1)(3,2,1), (1,4,1)(1,4,1), (4,3,1)(4,3,1), (1,5,1)(1,5,1), (5,4,1)(5,4,1), (5,2,1)(5,2,1), (2,4,2)(2,4,2). Hence the answer is 99.

Solution

Program Python:

t=int(input())
for i in range(t):
    n=int(input())
    k=0
    for c in range(1,n+1):
        for b in range(2*c, n + 1,c):
            k+=((n-c)//b)+1 
                
    print(k)

Program C++:

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    int cnt=0;
	    for(int i=1;i<=n;i++)
	    {
	        for(int j=i;j<=n;j+=i){
	            if(j%i==0)
	            {
	                for(int k=i;k<=n;k+=j)
	                {
	                    if(k%j==i) cnt++;
	                }
	            }
	        }
	    }
	    cout<<cnt<<endl;
	}
	return 0;
}