ABC156 F - Modularness

题目链接

题意还是比较清楚的，给你q个询问，对每组询问的模数和初始值不同，求满足条件\(a_j~\textrm{mod}~m_i < a_{j + 1}~\textrm{mod}~m_i，(0 \leq j < n_i - 1)\)的j的个数

正向不好求解，那我们可以反着找，也就是找满足条件\(a_j~\textrm{mod}~m_i \geq a_{j + 1}~\textrm{mod}~m_i，(0 \leq j < n_i - 1)\)的个数

\(a_j~\textrm{mod}~m_i = a_{j + 1}~\textrm{mod}~m_i\)时，只有当\(d_i=0\)的时候满足条件，统计个数即可

\(a_j~\textrm{mod}~m_i > a_{j + 1}~\textrm{mod}~m_i\)时，由于\(a_i\)是递增的，那么他只有在\(a_{i+1}>m, a_i<m\)的时候满足这个条件，因为对m取模，也就是说，每满足一次这个条件，\(\sum d_i\)除以m的商都会增加1

因为n远大于k，那我们可以只求一次k，然后找有几次循环，最后再加上不足k的那一次就行了

#include<bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x)&(-x))

typedef long long LL;

int d[5005];

void run_case() {

    int k, q;

    cin >> k >> q;

    for(int i = 0; i < k; ++i) cin >> d[i];

    while(q--) {

        int n, x, m;

        cin >> n >> x >> m;

        x %= m;

        LL sum = 0, zero = 0;

        for(int i = 0; i < k; ++i) {

            sum += (d[i] % m);

            zero += (d[i] % m == 0);

        }

        LL large = 1LL*((n-1)/k)*sum;

        zero = zero*((n-1)/k);

        for(int i = 0; i < n-1-((n-1)/k)*k; ++i) {

            large += (d[i] % m);

            zero += (d[i] % m == 0);

        }

        cout << n-1-(large+x)/m-zero << "\n";

    }

}

int main() {

    ios::sync_with_stdio(false), cin.tie(0);

    cout.flags(ios::fixed);cout.precision(10);

    run_case();

    cout.flush();

    return 0;

}

巴特西

ABC156 F - Modularness

最新文章

热门文章