# ODINSONS - Editorial

Author: tensor_14
Tester: iamreally_john
Difficulty: Medium-Hard

# Prerequisites:

Number Theory, Greedy

# Problem:

Given two a and b and operations:

1. Subtract 1 from a, making it one unit smaller.

2. Choose any integer p from 2 to k. And, subtract the number (a \mod p) from a.

Find the number of times the given operations to be performed on a to make a==b.

# Explanation:

Let L be LCM of all numbers in \begin{bmatrix} 2, &k \end{bmatrix}.
Two cases arise:
Case 1: a % b==0, hence we can’t decrease it using the second operation.

Case 2: a % L!=0. From Case 1, it follows that the optimal transformation will have all numbers divisible by L in \begin{bmatrix} b, & a \end{bmatrix}. We can split the sequence \begin{bmatrix} b, & a \end{bmatrix} into several intervals between the numbers divisible by L(the last interval may have a size less than L). Solve for all the intervals: First interval, last interval, and all intervals in middle. Be vigilant while solving the intervals when there are only 1 or 2 intervals.

At last, multiply the last result by the number of intervals excluding the first and last one. Further, add up obtained 3 values.

Note: You can use BFS to solve problems for one interval. And, further, use DP.
Time Complexity: O\left ( L \right )

# Solution:

Setter's Solution
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"

ll gcd(ll, ll);
ll timeTaken(ll, ll);

ll a, b, k, dp;

void solve(){
ll i, j;
cin>>a>>b>>k;
ll lcm = 1;
for(i = 2; i <= k; i ++)
lcm = lcm * i / gcd(lcm, i);

ll sol = 0,A = a / lcm, B = b / lcm;
sol = (A == B) ? timeTaken(a,b) : timeTaken(a % lcm,0) + (A-B-1) * (timeTaken(lcm-1,0) + 1) + timeTaken(lcm-1,b % lcm) + 1;

cout << sol << endl;
}

int main(){
ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());

int t = 1;
cin >> t;
while(t--){
solve();
}

return 0;
}

ll gcd(ll a,ll b){
return (b == 0)? a : gcd(b, (a % b));
}

ll timeTaken(ll x, ll b){
ll res = 0;

while (x != b){
ll i, nx = x-1,t;
for(i = 3; i <= k ; i ++)
if ((t = x / i * i)>= b && t < nx)
nx = t;
x = nx;  res ++;
}

return res;
}