F - Modularness

题意

图片说明
有q组数据，开始给K个数，然后给q组n，x，m
让计算出在递推式中，有多少项他在模m之后是小于后一项的。

分析

这题我参考了这篇博客：传送门
我们知道这个递推式就是第0项是x，然后后面依次是上一项加上d，d往后顺延，加完最后一个d，又开始从第一个开始加。很显然，这是一个递增的函数。
题目中让我们求的数量，那我们可以尝试先求出和

前一项等于后一项

我们知道后一项就是在前一项的基础上+d,如果d = 0的话，前一项就等于后一项，所以我们只要统计在运算过程中加了多少次d = 0.

前一项大于后一项

我们首先把所有的d都%m，然后进行算前缀和，只要前一项是小于k被m，后一项大于k倍m，那么在模m之后，前一项必定大于后一项，因为他两的差为d，d是小于m的。所以只要经过了多少个m，只需要最后一项前缀和/m就可以了。所以我们可以在每一组数据处理出K项前缀和，和K项0的个数前缀和。在计算前n项的时候，就可以把前K倍计算出来，然后不足K倍的单独计算。注意，要把第0项x加一次

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e4+10;

ll arr[maxn];
int K,Q,n,x,m;
ll sum[maxn],zero[maxn];
ll fun(){
    x%=m;
    ll cnt = n-1;//小于，大于，等于的总个数
    for(int i = 1;i<=K;i++){ //计算k长度的前缀和
        sum[i] = sum[i-1] + arr[i]%m;
        zero[i] = zero[i-1] + (arr[i]%m == 0);
    }
    ll cnt1 = (n-1)/K*zero[K]+zero[(n-1)%K];//K的倍数*K长度中有多少个0+不足K倍中的0个数
    ll cnt2 = ((n-1)/K*sum[K]+sum[(n-1)%K] + x )/m;//K的倍数*K长度的和+不足K倍的和+x
    return cnt-cnt1-cnt2;
}
int main(){
    cin>>K>>Q;
    for(int i = 1;i<=K;i++) scanf("%lld",&arr[i]);
    while(Q--){
        scanf("%d%d%d",&n,&x,&m);
        printf("%lld\n",fun());
    }
    return 0;
}