提交时间:2024-11-12 14:32:12
运行 ID: 34650
#include<bits/stdc++.h> #define int long long using namespace std; const int mod=1e9+7; void textread(){ freopen("test.in","r",stdin); freopen("test.out","w",stdout); } void textread2(){ freopen("alice.in","r",stdin); freopen("alice.out","w",stdout); } int quick_pow(int x,int y){ if(y==0)return 1; if(y==1)return x; if(y%2)return (((quick_pow(x,y/2)*quick_pow(x,y/2))%mod)*x)%mod; else return (quick_pow(x,y/2)*quick_pow(x,y/2))%mod; } int solve(int x){ if(x==0)return 0; if(x==1)return 1; if(x==2)return 3; int l=0,r=100000000; while(l<r){ int mid=l+r+1>>1; int ll=l,rr=r; if(mid*mid+mid<=x)l=mid; else r=mid-1; if(ll==l&&rr==r)break; } int k=0; for(int i=r+500;i>=l;i--){ if(i*i-i+1<=x){ k=i; break; } } k--; int res=0; if(k==1)res=3; else if(k%2==0){ int num=k/2; res-=(((((4*(num-1)*(num))%mod*(num*2-1)%mod)+15*num)%mod)+18*num*(num-1))%mod; res=(res+mod)%mod; }else{ int num=k/2; res-=(((((4*(num-1)*(num))%mod*(num*2-1)%mod)+15*num)%mod)+18*num*(num-1))%mod; res=(res+mod)%mod; res+=k*((k*k%mod+(k-1)*(k-1)%mod+k*2%mod)%mod)%mod; if(res<=0)res=(res+mod)%mod; else res%=mod; } k++; if(k*k-k+1<=x){ if(k%2==1){ int len=x-(k*k-k+1)+1; res+=(len*(x+(k*k-k+1)%mod)/2)%mod; if(res<=0)res=(res+mod)%mod; else res%=mod; }else{ int len=x-(k*k-k+1)+1; res-=(len*(x+(k*k-k+1)%mod)/2)%mod; if(res<=0)res=(res+mod)%mod; else res%=mod; } } return res; } int quick_sum[1000010]; signed main(){ ios::sync_with_stdio(0); //textread2(); int l,r; cin>>l>>r; cout<<(solve(r)-solve(l-1)+mod)%mod; return 0; }