ODINSONS - Editorial

editorial
, , ,
1

Problem Link: ODINSONS

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[16];

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;
}