It seems to be optimal to greedily choose the training in which the delta of STR is the smaller. Actually this is correct. However, if you naively perform the simulation, you will get TLE. Let us consider more deeply.

It is optimal to go to Kakomon gym several times, and then go to AtCoder gym several times.

The justification is as follows: if he goes to Kakomon gym after going to AtCoder gym, the STR transits as \(Z \to Z+B \to AZ+AB\), but the resulting STR is equal to the STR when he “goes to Kakomon gym once, and then goes to AtCoder gym \(A\) times,” in which he can obtain more EXP.

Since he can go Kakomon gym no more than \(\log_A Y \leq 64\) times, so the answer can be found in a total of \(O(\log_A Y)\) time by first simulating the process of going to Kakomon gym and then finding the number of remaining number of times to go to AtCoder gym in a \(O(1)\) time.

When implementing, be careful of overflows.

Sample Code (Python)

x,y,a,b=map(int,input().split())

ans=0
while a*x<=x+b and a*x<y:
  x*=a
  ans+=1

print(ans+(y-1-x)//b)

Sample Code (C++)

#include<iostream>
using namespace std;

int main(){
	long long x,y,a,b;
	cin >> x >> y >> a >> b;
	long long ans=0;
	while((double)a*x<=2e18 && a*x<=x+b && a*x<y){
		x*=a;
		ans++;
	}
	cout << ans+(y-1-x)/b << endl;
}