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

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

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

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

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

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

Code：Code：Code：

#include
using namespace std;
#define int long long 
#pragma GCC optimize(3)
typedef pairPII;
#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"<ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int _=1;cin>>_;while(_--){cf();}return 0;
}