题解 | #琪露诺的连续取模求和#
第一步:简化取模链
题目要求计算 。
让我们分析这个操作序列的性质。假设初始余数
,此时
。
接下来的模数依次是
。
-
情况 A:如果
由于模数序列是从
递减到
,且
,这意味着序列中所有的模数都严格大于
。 对于任何
,都有
。 因此,如果
,经过这一连串取模后,结果仍然是
。
-
情况 B:如果
此时
处于区间
之间。 在模数序列
中,必然存在一个模数
恰好等于
(因为
就在这个范围内)。 当运算进行到
这一步时,结果变为
(因为
)。 一旦结果变为
,后续无论模数是多少,结果都保持为
。
结论: 原式可以简化为一个分段函数:
第二步:转化求和问题
问题转化为:计算区间 内,满足
的所有
的和。
利用前缀和的思想,我们可以将区间求和
转化为两个从 1 开始的求和相减:
其中 表示计算区间
的累加和。
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll Calc(ll n, ll p, ll q) {
ll sum = 0;
ll k = n / q;
sum += k * p * (p - 1) / 2;
ll rem = n % q;
ll limit = min(rem, p - 1);
if (limit >= 1)
sum += limit * (limit + 1) / 2;
return sum;
}
void solve() {
ll l, r, p, q;
cin >> l >> r >> p >> q;
ll ans = Calc(r, p, q) - Calc(l - 1, p, q);
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
算法编程训练 文章被收录于专栏
各类牛客算法编程训练联赛、集训营
查看5道真题和解析