题目描述
给定一个长度为n的序列$a_1,a_2...a_n$，其中每个数都是正整数。
你需要找出有多少对(i,j)，$1 \leq i \leq j \leq n$且$gcd(a_i,a_{i+1}...a_j)~xor~(a_i~or~a_{i+1}~or~...~or~a_j)=k$，其中xor表示二进制异或，or表示二进制或。
输入输出格式
输入格式：
第一行两个整数n、k。
第二行n个整数$a_1,a_2...a_n$。
输出格式：
输出合法的(i,j)的对数。
输入输出样例
输入样例#1： 复制
5 6
2 4 3 4 2
输出样例#1： 复制
8
说明
对于30%的数据，$n \leq 500$。
对于60%的数据，$n \leq 100000$。
对于100%的数据，$1 \leq n,a_i \leq 500000$。
先枚举左端点，显然随着右端点右移，gcd不会增加，or不会减小
而且gcd每次减小最大为原来1/2，所以相同的gcd共可以分成logn块，实际上远远达不到
还有一个性质a^b^a=b
所以gcd^or^gcd=k^gcd=or
这样对于gcd相同的区间，用二分求出符合条件的or数量
用ST表维护x～y的gcd和or，而且了log要预处理，这样会快一些
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long lol;
int GCD[][],OR[][],Log[],n,k;
lol ans;
int gcd(int a,int b)
{
if (!b) return a;
return gcd(b,a%b);
}
int getg(int x,int y)
{
int d=Log[(y-x+)];
return gcd(GCD[x][d],GCD[y-(<<d)+][d]);
}
int getor(int x,int y)
{
int d=Log[(y-x+)];
return OR[x][d]|OR[y-(<<d)+][d];
}
int find(int x,int l,int g)
{
int r=n,as=l;
while (l<=r)
{
int mid=(l+r)/;
int G=getg(x,mid);
if (G==g) as=mid,l=mid+;
else r=mid-;
}
return as;
}
void query(int d,int x,int l,int r)
{
int L=l,R=r,as1=,as2=-;
while (l<=r)
{
int mid=(l+r)/;
int o=getor(x,mid);
if (o==d) as1=mid,r=mid-;
if (o<d) l=mid+;
if (o>d) r=mid-;
}
while (L<=R)
{
int mid=(L+R)/;
int o=getor(x,mid);
if (o==d) as2=mid,L=mid+;
if (o<d) L=mid+;
if (o>d) R=mid-;
}
ans+=as2-as1+;
}
int main()
{int i,x,pos,j;
cin>>n>>k;
for (i=;i<=n;i++)
{
scanf("%d",&x);
GCD[i][]=x;
OR[i][]=x;
}
for (i=;i<=n;i++)
Log[i]=Log[i/]+;
for (i=;i<=;i++)
{
for (j=;j<=n;j++)
if (j+(<<i)-<=n)
{
GCD[j][i]=gcd(GCD[j][i-],GCD[j+(<<i-)][i-]);
OR[j][i]=OR[j][i-]|OR[j+(<<i-)][i-];
}
}
for (i=;i<=n;i++)
{
for (j=i;j<=n;j=pos+)
{
int g=getg(i,j);
pos=find(i,j,g);
query(g^k,i,j,pos);
}
}
cout<<ans;
}