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Â
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:
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; }
Codechef Long Challenges
August Long Challenge 2021 Solutions
- Olympics Ranking
- Problem Difficulties
- Chef and Bulb Invention
- Array Filling
- Special Triplets
- Geometry 1
- Charge Scheduling
- Chef and Digits of Large Numbers
- Fat Hut
- Alternating LG Queries
July Long Challenge 2021 Solutions
- Maximum Production
- Relativity
- XxOoRr
- Optimal Denomination
- K Path Query
- Chef vs Bharat
- Chef and Pairs
- Even Odd Partition
- Dakimakura Distribition
- Madoka and Ladder Decomposition