标签：数论，分治
题目
1.1 backgrounds 小O是一个很萌很萌的女孩子 1.2 content 作为一个很萌很萌的女孩子，小O有很多很多美丽的宝石。 有一天，小O将她的宝石排成了一排一共n堆，第一堆有1个宝石，之后 每一堆的宝石数目是前一堆的两倍。 但是小O发现她的宝石不够用了，于是小O决定将每堆的宝石数量对一 个正整数M取模。 趁小O出去玩的时候，小Y偷偷地把这n堆宝石的顺序打乱了。 现在小O想把这些珠子变回原来的顺序。 小O想知道M最小是多少。 数据保证一定有解。 1.3 input format 第一行包含一个整数n 第二行n个整数ai，表示打乱顺序后第i堆宝石的数量。 1.4 output format 一行一个正整数M，表示答案。 1.5 sample input 5 1 2 3 4 8 1.6 sample output 13 1.7 constraints 对于20% 的数据，保证n ≤ 10 对于另外30%的数据，保证答案一定为奇数。 对于100% 的数据，1 ≤ n ≤ 2×10^5 , 0 ≤ ai ≤ 10^18
分析
考试的时候我乱搞竟然得了80pts,震惊
还有人暴力+随机化判断是否合法AC的（早知道我也去试试运气了，貌似大概率正确）
首先令$M=2^pq$（p可以为0，q为奇数） 假设M中含有因子2。 那么ai中除了1，其他数均为偶数。(觉得不显然的可以手动弄几个M玩一玩） 那么我们把这个1去掉，并且其他数全除以2，那么就变成了一个n=n-1,M=M/2的子问题。 经过一番操作，变成了一个M为奇数的问题。 对于M是奇数，我们找出ai中最大的奇数，最大的偶数以及次大的偶数。 然后将（偶数2-奇数）作为M check一下，取最小的合法M。 为什么这样做： 我们考虑一下模M意义下，宝石堆的宝石数是怎么样的。 大约长这样 b1 b1*2 b1*4 …… b2 b2*2 b2*4 …… 其中 bi=b[i-1]2^x-M 我们按有没有撞顶分成若干个子列。 那么每个奇数就是每个子列的第一个。 我们找出最大的奇数，那么考虑这个奇数是怎么来的。 显然是由它前面一个子列的末尾那个偶数2-M得到的。 并且那个偶数一定是最大或者次大。（可以想一想为什么）
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=3e5+6;
ll a[maxn],b[maxn],c[maxn],ans;
int vis[maxn],n,m=0;
bool ok(ll ans){
c[1]=1%ans;
rep(i,2,n)c[i]=(c[i-1]*2)%ans;
sort(c+1,c+n+1);
rep(i,1,n)
if(a[i]!=c[i])return 0;
return 1;
}//判断当前答案是否合法
void doit(){
ll ji=0,ou1=0,ou2=0;
rep(i,1,m){
if(b[i]&1)ji=max(ji,b[i]);
else{//寻找最大的奇数，最大和次大的偶数
if(ou1<b[i])ou2=ou1,ou1=b[i];
else if(ou2<b[i])ou2=b[i];
}
}
if(ou2!=0){
ll Q=(ou2*2-ji);
if(ok(Q*ans)){ans=Q*ans;return;}
}
if(ou1!=0){
ll Q=(ou1*2-ji);
if(ok(Q*ans)){ans=Q*ans;return;}
}//找到一个最小的合法M
}
int check(int x){
ll tmp=1LL<<x,y=tmp/2;int cnt=0,re=0,z=n;
rep(i,1,n)
if(!vis[i])
if(a[i]%tmp==y)cnt++;
if(cnt==1)re=1;if(re!=1)return re;
rep(i,1,n){
if(vis[i]){z--;continue;}
if(a[i]%tmp==y){vis[i]=true;z--;}
}
if(z==0)re=2;
return re;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
n=read();
rep(i,1,n)a[i]=read();
sort(a+1,a+1+n);
if(a[1]==0){ans=1;if(a[n]!=0)ans=a[n]*2;cout<<ans<<endl;return 0;}//特判M为2^x的特殊情况
int now=0;
while(1){
int ret=check(now+1);
if(ret==2){cout<<a[n]+1<<endl;return 0;}
if(ret==1)now++;else break;
}
rep(i,1,n)
if(!vis[i])b[++m]=a[i];
ans=1LL<<now;
rep(i,1,m)b[i]/=ans;//转化为奇数的子问题
doit();
cout<<ans<<endl;
return 0;
}
