FNDTRIP Editorial

general
, ,
1

PROBLEM LINK:

Induction Code Battle

Author: Tejus Kaw

Tester: Tejus Kaw

Editorialist: Saksham Aggarwal

DIFFICULTY:

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