寒假训练15-BCPC2023finla

I. 请问您今天要来点取模吗？

题意：求L-R里所有数经过一系列取模后的值的和

题解：我们考虑一个0-R的区间 经过一次对x的取模，会变成（R+1）/x个 0-（x-1）的区间以及可能会有尾巴上一个不完全的0-R%x的区间

前面这些所有区间可以看成一个一样的东西存在数据结构中，那么q次取模只会产生q个区间，我们用一个优先队列去储存它，每次pop出R最大的区间 然后拆分区间 最后对所有区间进行等差数列求和就行了 复杂度nlogn

代码：

#include<bits/stdc++.h>
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN =  3e5+7;
const ll mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
#define int ll
int a[MAXN];
int n;
int calc(int x) {
    if(x<=0) return 0;
    priority_queue<array<int,2>,vector<array<int,2>>> que;
    que.push({x,1});
    for(int i=1; i<=n; i++) {
        int tot=0;
        while(que.size()&&(que.top()[0]>=a[i])) {
            int now=que.top()[0];
            int cnt=que.top()[1];
            int num= (now+1)/a[i];
            que.pop();
            int tmp=num*cnt;
            if(tmp>=mod) tmp%=mod;
            //que.push({a[i]-1,tmp});
            tot+=tmp;
            if(tot>=mod) tot%=mod;
            if(now%a[i]!=a[i]-1) {
                que.push({now%a[i],cnt});
            }
        }
        if(tot)
        que.push({a[i]-1,tot});
    }
    int sum=0;
    while(que.size()) {
        int now=que.top()[0];
        int cnt=que.top()[1];
        que.pop();
        if(now>=mod) now%=mod;
        if(cnt>=mod) cnt%=mod;
        int tmp=(now*(now+1))/2;
        if(tmp>=mod) tmp%=mod;
        sum+=tmp*cnt;
        if(sum>=mod) sum%=mod;
    }
    return sum;
}
void solve() {
    int l,r;
    cin>>n>>l>>r;
    for(int i=1; i<=n; i++) cin>>a[i];
    int ans=calc(r)-calc(l-1);
    ans%=mod;
    ans+=mod;
    ans%=mod;
    cout<<ans<<"\n";
}
signed main() {
    close;
    solve();
}
/*
3 0 100
10 8 5

1 0 100
10
*/