 # FNDTRIP Editorial

Induction Code Battle

Author: Tejus Kaw

Tester: Tejus Kaw

Editorialist: Saksham Aggarwal

EASY-MEDIUM

# PREREQUISITES:

Math: Modulus function and divisors

# PROBLEM:

Given an integer N, find the number of triplets (A,B,C) such that

• AmodB=C
• BmodC=0
• 1≤A,B,C≤N

# QUICK EXPLANATION:

As AmodB=C, we can say B>C. Also, as BmodC=0, B is a multiple of C.

Since AmodB=C, we can say that A=k1*B+C. Also, as B is a multiple of C, so B=k2*C. Here, k1 and k2 are constants.

Using these two equations, find the number of possible values of triplets (A,B,C).

# EXPLANATION:

Fix the value of B. Smallest possible value of B will be 2 as C<B and C>=1. Now, as C is a divisor of B (BmodC=0), find the number of possible values of C by keeping B constant. The values of C will be divisors of B which can be found in O(sqrt N) time.

Now, we need to count the number of A, keeping B and C constant, such that 1≤A≤N and A=k1*B+C. Here, 0≤k1 and k1∗B+C≤N, which implies 0≤k1≤N-C/B. Hence, there are 1+⌊N-C/B⌋ possible values for A.

Hence, we can loop over all pairs (B,C) and sum over the number of possible values found for A for each pair (B,C).

This solution will take time O(N * sqrt N), as there are O(N) possible values for B and for each B, it takes O(sqrt N) time to iterate over possible values of C.

# ALTERNATE EXPLANATION:

This problem can also be solved by first fixing C instead of B and then finding the number of multiples of C.

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define rep(i, x, n) for(ll i = x; i < n; i++)
typedef long long int ll;

int main() {
ll t;
scanf("%lli", &t);
while(t--) {
ll n;
scanf("%lli", &n);
ll ans = 0;
rep(b, 1, n+1) for(ll c = 2*b;c <= n; c += b) {
ans += 1+(n-b)/c;
}
printf("%lli\n", ans);
}

}
``````
Editorialist's Solution
``````#include<cstdio>
#include<iostream>

using namespace std;

int t;

int main()
{
cin>>t;
while(t--){
int n,ans = 0;
scanf("%d",&n);
for(int b=1;b<=n;b++){
for(int c=2*b;c<=n;c+=b){
ans += 1 + (n-b)/c;
}
}
cout<<ans<<endl;
}
return 0;
}
``````
1 Like