代码

#include<iostream>
#define int long long
using namespace std;
const int mod=1e9+5;
int t,k;
int dp[100005],ps[100005];
signed main(){
    cin>>t>>k;
    for(int i=0;i<=k-1;i++) dp[i]=1;
    for(int i=k;i<=100000;i++){
        dp[i]=dp[i-1]+dp[i-k];
        dp[i]%=mod;
    }
    for(int i=1;i<=100000;i++){
        ps[i]=ps[i-1]+dp[i];
        ps[i]%=mod;
    }
    while(t--){
        int x,y;
        cin>>x>>y;
        cout<<ps[y]-ps[x-1]<<endl;
    }
    return 0;
}

评测结果