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