妹纸

NC15675. 妹纸

描述

XHRlyb发明了一类数，叫做妹纸数。

假设xi∈[p,q]，yi∈[u,v]，且xi与yi均为整数，我们称这区间[p,q]相对于区间[u,v]的妹纸数为

$\sum\limits_{i = p}^{q}i\ mod\ v\ mod\ (v - 1)\ mod\ ...\ mod\ u$

XHRlyb想让Cwbc帮她快速计算多组区间(a,b]相对于区间[l,r)的妹纸数。
Cwbc显然是愿意帮助她的，但他知道你不想解决这个问题，于是就把这个问题交给了你。
聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！

输入描述

输入数据有多行，每行有四个整数，a，b，l，r。

输出描述

输出数据应有多行，每行有一个数，表示答案。

示例1

输入:

2 3 1 2

输出:

说明:

任何数对1取模后的结果都为0。

示例2

输入:

3 6 2 4

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 5ms, 内存消耗: 484K, 提交时间: 2020-11-07 09:50:33

#include <bits/stdc++.h>
using namespace std;
long a,b,l,r;
long Sum(long x) {
    return x*(x+1)>>1;
}
long s(long x) {
    return Sum(l)*(x/r)+Sum(min(x%r,l));
}
int main() {
    while (cin>>a>>b>>l>>r) {
        l--,r--;
        cout<<(s(b)-s(a))<<endl;
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 9ms, 内存消耗: 488K, 提交时间: 2020-04-05 09:32:31

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,l,r;
ll cal(ll n){
    return n*(n+1)>>1;
}
ll sum(ll n){
    return cal(l-1)*(n/(r-1))+cal(min(n%(r-1),l-1));
}
int main(void){
    while(cin>>a>>b>>l>>r){
        cout<<sum(b)-sum(a)<<endl;
    }
}