本文共 1137 字，大约阅读时间需要 3 分钟。

题意：给定一个Arr[n],求满足multipul[L,R]/sum[L,R]==k的区间个数

思路：对于a[i]==1的情况，因为对multipul是没有影响的，只影响L,R。那么对于连续的区间1我们就可以跳，只要sum[L,R]∈[sum/multiple,sum/multiple+ lenof[1] ]。根据数据有multipul不会超过2e18。那么根据以上的做法，因为每次乘的数都是≥2的，第二层while循环的次数不会超过61次。复杂度为O(60*n);

#include
   
    #define PI acos(-1.0)#define pb push_back#define F first#define S secondusing namespace std;typedef long long ll;const int N=2e5+5;ll a[N],sum[N],jump[N],ans=0;int main(void){    ios::sync_with_stdio(false);    cin.tie(0);cout.tie(0);    ll n,k;    cin>>n>>k;    for(int i=1;i<=n;i++)   cin>>a[i];    for(int i=1;i<=n;i++)   sum[i]=sum[i-1]+a[i];    jump[n]=n;    jump[n+1]=n+1;    for(int i=n-1;i>=1;--i){        if(a[i]==1) jump[i]=jump[i+1];        else    jump[i]=i;    }    for(int i=1;i<=n;i++){        ll mul=1;        int j=i;        int last=i;        while(j<=n&&(ll)2e18/a[j]>=mul){            /// last to j            mul*=a[j];            ll presum=sum[j]-sum[i-1];//            if(j==i&&mul/presum==k)    ans++;            last=j;            j=jump[j+1];            if(mul%k==0&&mul/k>=presum&&mul/k<=presum+j-last-1)ans++;//            cout <
    
     <<" "<
     
      <
     
    
   

转载地址：http://oykiz.baihongyu.com/