CF1804C Pull Your Luck 题解

题面。

翻译清晰，这里就不吐槽了。

根据轮盘转动的方法，可以看出这是一个简单的高斯求和。

因为这是一个轮盘，在轮盘中转动了 \(now\) 个格子与转动了 \(now \bmod n\) 所到达的格子是一样的（这就没必要证明了吧），因此我们很容易就能得到一个最朴素的代码：

	cin >> T;
	while(T--)
	{
		cin >> n >> x >> p;
		ll flag = 0;
		fr(i , 1 , p)
		{
			ll now = (1 + i) * i / 2;
			if((x + now) % n == 0)
			{
				printf("Yes\n");
				flag = 1;
				break;
			}
		}
		if(!flag)
		{
			printf("No\n");
		}
	}

然后非常愉快地在第二个点超时。

回看数据才发现 \(p \le 10^9\)……

我们要解决的其实就是 \(p\) 的上界，下界没得商量，从 \(1\) 开始。

不妨多出几组小数据模拟一下就会发现，\(p\) 的上界与 \(n\) 貌似有点关系，当 \(p\) 超过某个值时，所能到达的格子便会开始陷入循环，只要找出这个值就解决问题了。

先列一个长度大于 \(n\) 的三倍的序列：

\(\displaystyle \frac{1 \times (1+1)}{2}\)，
\(\displaystyle \frac{2 \times (2+1)}{2}\)
……
\(\displaystyle \frac{n \times (n+1)}{2}\)，
……
\(\displaystyle \frac{2n \times (2n+1)}{2}\)，
……
\(\displaystyle \frac{3n \times (3n+1)}{2}\)……

这个序列其实就表示移动的步数，表示最终位置需要化简并对 \(n\) 取模，得到通项公项：

\(\displaystyle \frac{hi \times (hi+1)}{2} \bmod n\)，其中 \(1 \le i \le n\)，\(h \in N\)。

用来表示的字母没有特殊意义，不要追问 doge。

接下来只要找到最小的 \(h\) 满足 \(\displaystyle \frac{hi \times (hi+1)}{2} \bmod n=\displaystyle \frac{i \times (i+1)}{2} \bmod n\) 即可。

设存在一个数 \(k\)，使 \(\displaystyle \frac{ki \times (ki+1)}{2} \bmod n=\displaystyle \frac{i \times (i+1)}{2} \bmod n\)，其中 \(1 \le i \le n\)，在解出 \(k\) 后，\(p\) 的上界也可以确定。（其实 \(k\) 就是上面的 \(h\)）

解出 \(k\) 为大于 \(0\) 的 \(n\) 的偶数倍。所以 \(p\) 就只需要取 \(n\) 的偶数倍就行了。\(k\) 表示的其实就是能完成从 \(0\) 到 \(n-1\) 循环的数。

但是以上所有情况都是建立在一开始从零号位开始并且至少使用一点力气的情况下。实际上并不一定是从零开始，在通过上述方式算出 \(p\) 后，减去初始的格子位置，也是题目中的 \(x\)，才最符合推理。（其实减不减去 \(x\) 都无所谓，只是减去后会严谨一点）

如果 \(p\) 本身就很小的话，也没有必要更新它的值。

代码

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define mod 1e9 + 7
#define fr(i , a , b) for(ll i = a ; i <= b ; ++i) //-(~i)
#define fo(i , a , b) for(ll i = a ; i >= b ; --i) //~(-i)
using namespace std;
inline ll QuickPow(ll a , ll b)
{
	if(b == 0)
	{
		return 1;
	}
	ll k = QuickPow(a , b >> 1);
	if(b & 1)
	{
		return k * k * a;
	}
	return k * k;
}
ll T , n , x , p;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	while(T--)
	{
		cin >> n >> x >> p;
		ll flag = 0;
		fr(i , 1 , min(p , 2 * n - x))
		{
			ll now = (1 + i) * i / 2;
			if((x + now) % n == 0)
			{
				cout << "Yes" << '\n'; 
				flag = 1;
				break;
			}
		}
		if(!flag)
		{
			cout << "No" << '\n';
		}
	}
	return 0;
}