[JZOJ4307]喝喝喝—枚举
题目链接
自行搜索
分析
我们需要找到所有不包含$(a_x,a_y),a_x \equiv k \mod a_y (x<y)$这样的连续数对,转化一下变成$a_x-k \equiv 0 \mod a_y$.
考虑从左到右加数,可以发现如果$a_i - k \equiv 0 \mod a_j$,那么起点为$i$,终点大于等于$j$的连续序列都是不合法的,于是维护一个左指针$lst$,表示当前距离最近的不合法起点,换句话说,$lst+1$到当前遍历的数这一段都是合法的
怎么更新$f[x]$?由于值域范围很小$(1e5)$,我们设若当前加的第$i$个数为$x$,设$f[x]$为当前距$i$最近的$y$使得$x - k \equiv 0 \mod a_y$,每次新加入一个数就比较$f[x]$与$lst$哪个更大,这样就能更新$lst$,同时加完$x$这个数后,我们可以在$O( \sqrt{x} )$的时间内将所有满足$x -k \equiv 0 \mod p$的$p$找出来更新它们的$f$值
当时要注意我们这种方法会漏掉前面有数为$k$的情况,要特判
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
inline char gc(){
static char buf[SIZE],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;
while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
const int maxn=1000005;
const int inf=0x7fffffff;
int f[maxn],kk=0,lst=0;
int n,k;
ll ans=0;
int main(){
int x;
FO(drink);
read(n),read(k);
for(ri i=1;i<=n;i++){
read(x);
if(x>k){
if(f[x]>lst)lst=f[x];
if(kk>lst)lst=kk;
}
ans+=i-lst;
if(x==k)kk=i;
else if(x<k)continue;
x-=k;
for(ri j=1;j<sqrt(x+0.5);j++){
if(x%j==0)f[j]=f[x/j]=i;
}
}
printf("%lld\n",ans);
return 0;
}
|