codeforces 992 D Nastya and a Game 【数论 暴力剪枝】

题目大意:
给你一个n,k ，接着给你n个数，让你找到这样一段连续子序列，ai, ai+1,……，aj ，使得这段序列的乘积p 除以 该序列的和s 的值恰好为k
n的数据范围为2e5 k的数据范围 1e5 ，ai的数据范围是1e8
题目分析
我们发现对于这个乘积p ，不可能无穷大，当我们取最大的s*k时也就是 1e8*2e5*1e5 =2e18，这个数据范围正好不超过longlong,那么我们假想一下，在一段子序列中大于1的数最多不会超过64个，那么我们只要枚举左端点，然后往后跳，跳到非1的数的位置，然后暴力判断即可。
题目难点：
这个题目有两个值得注意的点，一个就是ll溢出的判断，可以采用 LLONGMAX的方式，还可以采用转化成double的方式
还有就是跳跃的方式，可以用一个数组vis[i] 记录我们要跳跃的位置，vis[i+1]存储的坐标就是下一个非1的位置，我们只需要倒过来扫一遍就可以

代码：

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn=2e5+50;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
typedef long long ll;
ll n,k;
ll a[maxn];
int vis[maxn];
ll ans=0;
bool Overflow(ll x,ll y)
{
    if(x>LLONG_MAX/y)return false;
    else return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cl(vis);
    cl(a);
    cin>>n>>k;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    vis[n+1] = -1;
    for(int i=n; i>=1; i--)
    {
        if(a[i]>1) vis[i]=i;
        else vis[i]=vis[i+1];
    }
    ll p =1;
    ll s=0;
    for(int i=1; i<=n; i++)
    {
        int j=i;
        p=a[i];
        s=a[i];
        if(p==s*k)ans++;
        while(1)
        {
            int z = vis[j+1];
            if(z==-1)z=n+1;
            int ones = z-j-1;
            if(p%k==0&&p/k-s>=1&&p/k-s<=ones)
            {
                ans++;
            }
            if(z==n+1)break;
            if(Overflow(p,a[z]))
            {
                p = p*a[z];
                j = z;
                s = s + a[z] +ones;
                if(p == s * k) ans++;
            }
            else break;
        }
    }
    cout<<ans<<endl;
    return 0;
}