codeforces-922D-Nastya and a Game

传送门：https://codeforces.com/contest/992/problem/C

题意：找到给定的数组有多少子段的乘积/和==k

如果你注意了给出的数据及数据范围你就会发现，这个题他没有给mod？？？

这啥情况？？也就是说，一段数的乘积，最大不能超过long long ？？

这不就好说了吗，如果是乘1，那么乘积不会变，和会增加，对乘积没有贡献

如果乘2就是对乘积的最小贡献，即使这样最大也就 2^64 了，也就是说，他这个子段最大也就是60+个数，暴力的话，时间复杂度是o(64*n)

注意六十来个数是在没1的情况下，那怎么把1搞没呢

记录一个数往后第一个不是1的位置，把1跳过即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const ll maxx=1e18;
 5 ll a[200009][2];
 6 ll next_[200009];
 7 ll z[200009];//用栈找他后面第一个不是1的地方
 8 int main()
 9 {
10     ll n,k;
11     scanf("%lld%lld",&n,&k);
12     int top=0;
13     for(int i=1;i<=n+1;i++)
14     {
15         if(i==n+1) a[i][0]=2,a[i][1]=n+1;
16         else scanf("%lld",&a[i][0]),a[i][1]=i;
17         if(i==1) z[++top]=a[i][1];
18         else
19         {
20             while(top>0&&a[i][0]!=1)
21             {
22                 next_[z[top]]=i;
23                 top--;
24             }
25             z[++top]=a[i][1];
26         }
27     }
28     ll ans=0;
29     for(int i=1;i<=n;i++)
30     {
31         ll sum=0,muilt=1;
32         for(int j=i;j<=n;j=next_[j])//把1跳过
33         {
34             sum+=a[j][0];
35             if(muilt>maxx/a[j][0]) break;//用除法不然会炸
36             muilt*=a[j][0];
37             if(muilt%k==0&&sum*k<=muilt&&muilt<=(sum+(next_[j]-j-1))*k) ans++;
38             sum+=(next_[j]-j-1);
39         }
40     }
41     printf("%lld
",ans);
42     return 0;
43 }