Educational Codeforces Round 24 E. Card Game Again(双指针)

题目链接：Educational Codeforces Round 24 E. Card Game Again

题意：

给你n个数和一个数k。

现在每次可以拿掉前x个数，后y个数，剩下的数的乘积要能被k整除，求方案数。

题解：

首先剩下的数要被k整除，剩下数的乘积要有k的全部因子，并且个数要大于等于k。

所以可以将所有的数先和进行求gcd,只有这些gcd才有贡献。

然后对gcd进行分解。

然后就可以双指针跑一跑了，只要因子的个数大于等于k的因子个数了就加上n-r+1。

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 typedef pair<int,int>P;
 5 
 6 const int N=1e5+7;
 7 int n,k,x;
 8 map<int,int>cnt;
 9 vector<P>V[N];
10 int primes[N+1],tot=0;
11 bool vis[N+1];
12 void Euler(){
13     memset(vis,0,sizeof(vis));
14     F(i,2,N){
15         if(!vis[i])primes[++tot]=i;
16         F(j,1,tot){
17             if(i*primes[j]>N)break;
18             vis[i*primes[j]]=1;
19             if(i%primes[j]==0)break;
20         }
21     }
22 }
23 
24 void deel(int i,int x)
25 {
26     int ct=0;
27     F(j,1,tot)
28     {
29         ct=0;
30         if(primes[j]>x)break;
31         while(x%primes[j]==0)ct++,x/=primes[j];
32         if(ct)V[i].push_back({primes[j],ct});
33     }
34     if(x!=1)V[i].push_back({x,1});
35 }
36 
37 int check()
38 {
39     for(auto &it:V[0])
40         if(cnt[it.first]<it.second)return 0;
41     return 1;
42 }
43 
44 int main()
45 {
46     Euler();
47     scanf("%d%d",&n,&k);
48     F(i,1,n)scanf("%d",&x),x=__gcd(x,k),deel(i,x);
49     deel(0,k);
50     long long ans=0;
51     for(int l=1,r=1;r<=n;r++)
52     {
53         for(auto &it:V[r])cnt[it.first]+=it.second;
54         while(l<=r&&check())
55         {
56             ans+=n-r+1;
57             for(auto &it:V[l])cnt[it.first]-=it.second;
58             l++;
59         }
60     }
61     printf("%I64d
",ans);
62     return 0;
63 }

View Code