F - Modularness 题解

F - Modularness 题解

前言：

E题不知道为啥一眼秒，rk18。
F题不知道为啥想不出，rk193。

题目描述

先给k个数，a[0]~a[k-1]。
然后q次询问，每次给出n,x,m。
b[0]=x,b[i]=b[i-1]+a[(i-1)%k]。
问有多少i满足b[i]%m<b[i+1]%m。
k,q<=5000
n,x,m<=1e9

题解

首先很好想到,b[i]%m<b[i+1]%m的话，需要b[i]%m+a[i%k]<m。
我们不求<的个数而求>=的个数，=一定是a[i%k]%m=0，>就是b[i]%m<m且b[i]%m+a[i%k]>m
然后当时就想不出了，一直在想怎么求Sx%m<y。
我们要整体考虑，个数就是a[n-1]/m，为啥呢，就是每次>m个数都加1。
想到就是**题，没想到就gg。

代码

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int N=1e6+5;
int n,m,k,ans,inv[N],a[N],b[N];
char s[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
signed main()
{
    n=read();m=read();
    for(int i=0;i<n;i++)a[i]=read();
    while(m--)
    {
        int A=read(),B=read(),mod=read();
        int ans=0,S=0;
        for(int i=0;i<n;i++)
        {
            b[i]=a[i]%mod;
            if(b[i]==0)b[i]=mod;
            S+=b[i];
        }
        ans=B;
        ans+=S*((A-1)/n);
        for(int i=0;i<(A-1)%n;i++)ans+=b[i];
        printf("%lld\n",A-1-(ans/mod-B/mod));
    }
    return 0;
}