CF1482B Restore Modulo
知识点：
同余、（为什么不是GCD！） GCD（题解写到一半发现GCD也是正解！）
题目链接
题意
给你原不减等差数列每个元素取模后的序列，求满足题意的最大的模和公差，且公差小于模。不存在原序列输出-1，模无限大输出0。
思路
之前做过一道题：所有序列的元素取模后相等，求最大的模。
如出一辙啊，就是这道题的特殊情况（公差为零）。
于是我按照那题的思路用了半天的gcd
（题解写到此处的时候我发现有点不对劲，竟然把gcd解法调出来了！）
于是我按照那题的思路用了gcd解法，此题解为一题多解。
思路1（GCD）
在模系统中求最大模数，考虑GCD。
假设存在原序列a，则 a i + 1 − a i = a i − a i − 1 = ⋯ = d a_{i+1}-a_i=a_i-a_{i-1}=\dots=d ai+1−ai=ai−ai−1=⋯=d（d为公差），模系统中
a i + 1 − a i ≡ a i − a i − 1 ≡ ⋯ ≡ d ( m o d m ) a_{i+1}-a_i\equiv a_i-a_{i-1}\equiv \dots \equiv d\quad(mod\ m) ai+1−ai≡ai−ai−1≡⋯≡d(mod m)
从这个式子中求m仍然困难。转化为
( a i + 1 − a i ) − ( a i − a i − 1 ) ≡ 0 ( m o d m ) (a_{i+1}-a_i)-(a_i-a_{i-1})\equiv 0\quad(mod\ m) (ai+1−ai)−(ai−ai−1)≡0(mod m)
( a i − a i − 1 ) − ( a i − 1 − a i − 2 ) ≡ 0 ( m o d m ) (a_{i}-a_{i-1})-(a_{i-1}-a_{i-2})\equiv 0\quad(mod\ m) (ai−ai−1)−(ai−1−ai−2)≡0(mod m)
… \dots …
这里稍微总结一下与0和1同余情况下的意义：
a与0同余：a整除模
a与1同余：gcd(a,m)=gcd(a%m,m)=gcd(1,m)=1，即a与模互质。
即求最大的m使得所有 ≡ \equiv ≡左边的式子都整除m，此正为gcd的定义！
即求 m = g c d ( ( a i + 1 − a i ) − ( a i − a i − 1 ) , ( a i − a i − 1 ) − ( a i − 1 − a i − 2 ) , … ) m=gcd((a_{i+1}-a_i)-(a_i-a_{i-1}),(a_{i}-a_{i-1})-(a_{i-1}-a_{i-2}),\dots) m=gcd((ai+1−ai)−(ai−ai−1),(ai−ai−1)−(ai−1−ai−2),…)
c可取任意 a i − a i − 1 a_i-a_{i-1} ai−ai−1（不妨取 a 2 − a 1 a_2-a_1 a2−a1）的最小正整数解。
特判1：n<3时，必无限大（请手动模拟）
特判2：存在 a i ≥ m a_i\geq m ai≥m时，元素比模还大，无解（不明白为什么不能取m的因子）
思路2（同余）
观察一定公差小于模，所以序列上升部分后面一定是相对前面未取模的结果，易知 c = a i − a i − 1 c=a_i-a_{i-1} c=ai−ai−1，下降部分后面一定是相对前一元素取模的结果， a i − 1 + c ≡ a i ( m o d m ) a_{i-1}+c \equiv a_i\quad (mod\ m) ai−1+c≡ai(mod m)。
同样地， a i − 1 − a i + c ≡ 0 ( m o d m ) a_{i-1}-a_i+c \equiv 0\quad (mod\ m) ai−1−ai+c≡0(mod m)，说明 ≡ \equiv ≡左边的式子整除m，取m为 ≡ \equiv ≡左边的式子即为最大值。
求出c，m后检验整个序列即可。
特判1：n<3时，必无限大（请手动模拟）
特判2：存在 a i ≥ m a_i\geq m ai≥m时，元素比模还大，无解（不明白为什么不能取m的因子）
特判3：没有上升部分（求不出c）或没有下降部分（求不出m），可发现如果取模后是等差数列，m无限大，否则不存在原序列。
代码1（GCD）
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;
const ll N=2e5+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll n;
ll arr[N];
ll d[N];//d[i]=arr[i]-arr[i-1]
void solve()
{
scanf("%lld",&n);
for(ll i=1; i<=n; i++) scanf("%lld",&arr[i]);
if(n<3)//特判1
{
puts("0");
return;
}
for(ll i=2; i<=n; i++) d[i]=arr[i]-arr[i-1];
ll gcdd=0;//初始化无穷大
for(ll i=3; i<=n; i++)
{
ll val=abs(d[i]-d[i-1]);//负数整除m与正数整除m等价
if(val==0) continue;//防止gcd(0,0)RE
gcdd=__gcd(gcdd,val);
}
if(gcdd==0)//无穷大
{
puts("0");
return;
}
for(ll i=1;i<=n;i++)
{
if(arr[i]>=gcdd)//判断有没有比模还大的数
{
puts("-1");
return;
}
}
printf("%lld %lld\n",gcdd,((arr[2]-arr[1])%gcdd+gcdd)%gcdd);
//参数3为最小非负整数写法。
}
int main()
{
ll t;
scanf("%lld",&t);
while(t--)
solve();
return 0;
}
代码2（流行题解）
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;
const ll N=2e5+10;
ll n;
ll arr[N];
void solve()
{
scanf("%lld",&n);
for(ll i=1; i<=n; i++) scanf("%lld",&arr[i]);
if(n<3)
{
puts("0");
return;
}
//检验是否为等差数列
ll d=arr[2]-arr[1];//公差
bool f=false;
for(ll i=3; i<=n; i++)
{
if(arr[i]-arr[i-1]!=d)
{
f=true;
break;
}
}
if(!f)//公差相同
{
puts("0");
return;
}
ll c=-1;
for(ll i=2; i<=n; i++)
{
if(arr[i-1]<arr[i])//找到上升部分求c
{
c=arr[i]-arr[i-1];
break;
}
}
if(c==-1)//找不到
{
puts("-1");
return;
}
ll m=-1;
for(ll i=2; i<=n; i++)
{
if(arr[i-1]>arr[i])//找到下降部分求m
{
m=arr[i-1]-arr[i]+c;
break;
}
}
if(m==-1)
{
puts("-1");
return;
}
//检验是否存在比模还大的数
for(ll i=1; i<=n; i++)
{
if(arr[i]>=m)
{
puts("-1");
return;
}
}
//检验整个序列（模拟）
for(ll i=2; i<=n; i++)
{
if((arr[i-1]+c)%m!=arr[i])
{
puts("-1");
return;
}
}
printf("%lld %lld\n",m,c);
}
int main()
{
ll t;
scanf("%lld",&t);
while(t--)
solve();
return 0;
}
投递粉笔网等公司10个岗位 >
