B3830 回溯的雨 题解
Undertale_chara
·
·
题解
其实这是一道简单的数学结论题。
首先，不难得出 a_i=(c_i-y)/x，因为 x,y,a_i,c_i 均为正整数。
SO。
得出结论：若存在符合题意的序列 a 及正整数 y，则序列 c 中的元素为模 x 的同余类。
那么我们只需对 c 中的元素依次判断是否模 x 同余即可判断是否存在符合题意的序列及正整数 y。
其次，怎么求出 y 的最大值呢？
很简单，找出只要序列 c 的最小值，再运用我们之前的结论不难得出。
大功告成！
我的代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*快读*/
ll read()
{
ll x=0,w=1;
char c=0;
while(c<'0'||c>'9')
{
if(c=='-')
w=-w;
c=getchar();
}
while(c>='0'&&c<='9')
x=x*10+(c-'0'),
c=getchar();
return x*w;
}
/*快写*/
void write(ll x)
{
x<0?x=-x,putchar('-'):0;
static ll sta[35];
ll top=0;
do
sta[top++]=x%10,x/=10;
while(x);
while(top)
putchar(sta[--top]+'0');
}
ll n,x,c[100005];
int main()
{
n=read();x=read();
for(long long i=1;i<=n;++i)
cin>>c[i];
sort(c+1,c+1+n);
/*特判*/
if(c[1]<x)
write(-1),
exit(0);
/*判断同余*/
for(ll i=2;i<=n;++i)
if((c[i]-c[1])%x)
write(-1),
exit(0);
write(c[1]-x);
}
```