# August Long Challenge Special Triplets Solution

## 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

Subtask #3 (75 points): Original constraints

Sample Input 1

``````3
3
4
5
``````

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: Special Triplets Solution

``````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++: Special Triplets Solution

``````#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;
}``````