Nebius Welcome Round (Div. 1 + Div. 2) C 的证明

首先给出结论：最多暴力跑 $min(2*n,p)$ 便可知是否存在一个 $f<=p$ 使得 $val=$$\sum\limits_{i=1}^fi$ ，$val$ % $n=(n-x)$ % $n$。

证明：由等差数列公式我们可以得出 $val=$$\dfrac{(1+f)*f}{2}$

若 $n$ 为奇数，那么令 $f=n$，$\dfrac{1+n}{2}$ 为一整数，所以 $val$ % $n=0$ 等价于初始的状态，那么接下去如果令 $f>n$ ，出现的 $n+1、n+2、…$ 使其减去 $n$，等价于 $1、2、…$ 那么又回到了之前的环上，因此若 $n$ 为奇数，在 $p>=n$ 的情况下最多跑 $n$ 次即可判断出最终的结果。

若 $n$ 为偶数，那么至多需要跑 $2n$ 次可以判断出结果，因为$f=2n$，$val=$ $\dfrac{(1+2n)2n}{2}$，得知 $1+2n$ 为一整数。因此 $val$ % $n$ 等价于初始的状态。同样接下去如果令 $f>2n$ ，出现的 $2n+1、2n+2、…$ 使其减去 $2n$，等价于 $1、2、…$ 跑到了之前的环上。

综上：最多需要跑 $min(2*n,p)$ 既可知所需 $f$ 是否存在。

$Code：$

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#pragma GCC optimize(3)
typedef pair<int,int>PII;
#define pb push_back
void cf(){
    int n,x,p;
    cin>>n>>x>>p;
    int ans=0;
    for(int i=1;i<=min(2*n,p);i++){
        ans+=i;
        if(ans%n==((n-x)%n)){
            cout<<"Yes"<<endl;
            return ;
        }
    }
    cout<<"No"<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        cf();
    }
    return 0;
}