2023 江苏省赛
题目链接
B
对于 \(n\) 对关系 , 反过来考虑 \(b_{i} > b{i + 1}\)的个数
观察 \(bn\) 的形式 :
\(x ,\ x + a_{0} ,\ x + a_{0} + a_{1} \ ,\ .... ,\ x + a_{0} + ... + a_{n - 1}\)
其中 \(x,a_{i}\)均为模 \(m\) 后数 , 相当把外层取模内置(一定要算取模后的，不然后面的证明不成立)
那么可以想到一段成为 \(m\) 上如果 \(b_{i} = x + a_{0} + ... + a_{i - 1} < m\) , \(b_{i+1} = x + a_{0} + ... + a_{i}\) > m , 那么 \(b_{i}\) 一定在取模意义下大于 \(b_{i+1}\) ( $b_{i} + a_{i} > m $ 等价于 \(b_{i} > m - a_{i}\) , \(m - a_{i}\) 就是 \(b_{i}\) 对 m 取模) , 计算这样出现的次数即可 (\(b_{i+1}\)大于\(m\)说明到了下一段 \(m\)) , 计算这样出现的次数即可
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0);
int k;
cin >> k;
vector<ll> a(k);
for(int i = 0 ; i < k ; ++i)
cin >> a[i];
ll n,m,x;
cin >> n >> m >> x;
ll sum = 0;
for(int i = 0 ; i < k ; ++i) {
sum += a[i] % m;
}
ll bn = sum * (n / k) + x % m;
int pos = n % k;
for(int i = 0 ; i < pos ; ++i)
bn += a[i] % m;
cout << n - bn / m << '\n';
return 0;
}