FNDTRIP Editorial


Induction Code Battle

Author: Tejus Kaw

Tester: Tejus Kaw

Editorialist: Saksham Aggarwal




Math: Modulus function and divisors


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

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


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).


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.


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


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

using namespace std;

int t;

int main()
        int n,ans = 0;
        for(int b=1;b<=n;b++){
            for(int c=2*b;c<=n;c+=b){
                ans += 1 + (n-b)/c;
    return 0;
1 Like