本文距离上次更新已过去 0 天，部分内容可能已经过时，请注意甄别。

P10252 题解

一直没有想到 可能等于 ，白交了好多发，好蠢……

题意

题面很清楚了。

解析

有一个很且显然的想法是：每次 变换后，如果变换后的 ，那么 在接下来的变换里只会越来越大；反之亦然。具体的下面会提及。

找找规律：

变换一次：。
变换两次：。
变换三次：。
变换 次：。

嘶……没头绪。那看看每次 增加的量是多少：

可以看见 这个数是第一次变换后， 与 的差值。 的增加与否与前面的 无关（），只跟 有关，而 是一个定值。这也说明了开头猜想的正确性。

从这里我们可以发现一种特殊情况：如果 ，那么 变换后不可能变小，一开始的 就是最小值。这种情况直接输出 即可。

现在来考虑 的一般情况。我们要求记的毕竟不是增加量，而是想求出它每一次变换后 的大小。使用上面的差值求和试试看？记 为 ，设 为变换次数，那么变换 次后：

那么只要枚举 ，判断这个能在右边的式子是否小于 即可。 中的 增长速度很快（），不用二分就能过（或许可能数据太水了 = =）。

注意，这里的 为分母，需要特判 的情况。答案易知是 。还有一种特殊情况：当 或 时，直接输出 即可。

代码

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

typedef long long ll;
ll T, x, a, b;

ll qpow(ll a, ll b) // 快速幂 
{
	ll res = 1;
	while (b)
	{
		if (b & 1) res *= a;
		a *= a, b /= 2;
	}
	return res;
}

void solve()
{
	cin >> x >> a >> b;
	if (a * x - b >= x)
	{
		cout << x << endl;
		return ;
	}
	if (a == 0 || x == 0)
	{
		cout << -b << endl;
		return ;
	}
	if (a == 1)
	{
		cout << x - (x / b + 1) * b << endl;
		return ;
	}
	ll d = a * x - b - x;
	for (int i = 1; ; i++)
	{
		if (x + d * (qpow(a, i) - 1) / (a - 1) < 0)
		{
			cout << x + d * (ksm(a, i) - 1) / (a - 1) << endl;
			break;
		}
	}
	return ;
	
}

int main()
{
	cin >> T;
	while (T--)
		solve();
	
	return 0;
}