この問題はクエリごとに答えを二分探索することにより解けます。

レベル \(0\) のキャラクタをレベル \(X\) に上げるために必要な宝石の個数は \(\sum_{x=0}^{X-1}Ax+B=A\frac{X(X-1)}{2}+BX\) であるため、求める答えは \(A\frac{X(X-1)}{2}+BX \leq N\) を満たす最大の整数 \(X\) です。不等式の左辺は \(X\) の増加で狭義単調増加するため、二分探索によりそのような値を求めることができます。

実装によっては 64bit 整数ではオーバーフローすることがあるため注意してください。

writer解(C++)

#include<bits/stdc++.h>
using namespace std;

int solve(long long N,long long A,long long B){
	long long ok=0, ng=1;
	auto f=[&](long long x){return A*x*(x-1)/2+B*x;};
	while(f(ng)<=N)ng*=2;
	while(ng-ok>1){
		long long mid=(ok+ng)/2;
		if(f(mid)<=N)ok=mid;
		else ng=mid;
	}
	return ok;
}

int main(){
  int q;
  cin >> q;
  while(q--){
    long long n,a,b;
    cin >> n >> a >> b;
    cout << solve(n,a,b) << endl;
  }
}