822D - My pretty girl Noora - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> 
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ;
template<class T>
using max_heap = priority_queue<T,vector<T> >; 
template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T> >; 
 
template <typename T>
void dout(string name, T arg)
{
	cerr << "\e[91m" << name << " = " << arg << "\e[39m" << endl;
}
 
template <typename T1, typename... T2>
void dout(string names, T1 arg, T2... args)
{
	cerr << "\e[91m" << names.substr(0, names.find(',')) << " = " << arg << "   |   \e[39m";
	dout(names.substr(names.find(',') + 2), args...);
}
 
#ifdef LOCAL
#define debug(...) dout(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 42
#endif
 
template <class Ch, class Tr, class Container>
basic_ostream<Ch, Tr> &operator<<(basic_ostream<Ch, Tr> &os, Container const &x)
{
	os << "{ ";
	for (auto &y : x)
		os << y << " ; ";
	return os << "}";
}
 
template <class X, class Y>
ostream &operator<<(ostream &os, pair<X, Y> const &p)
{
	return os << "[ " << p.first << ", " << p.second << "]";
}
 
typedef pair<long long int, long long int> ii;
typedef vector<long long int> vi;
typedef vector<vector<long long int>> vvi;
typedef vector<pair<long long int, long long int>> vii;
 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(c) (c).begin(), (c).end()
#define sz(a) ((long long int)(a).size())
#define lli long long int
#define ull unsigned long long int
#define ld long double
#define ref(i, x, y) for (long long int i = (x); i <= (y); ++i)
#define reb(i, x, y) for (long long int i = (x); i >= (y); --i)
#define trf(c, it) for (auto it = (c).begin(); it != (c).end(); ++it)
#define trb(c, it) for (auto it = (c).end() - 1; it != (c).begin() - 1; --it)
#define tc(t) int t; cin >> t; while (t--)
#define endl '\n'
 
const long long int mod = 1e9 + 7;
const long long int pinf = 9223372036854775807;
const long long int ninf = -9223372036854775807;
 
/*/----------------------------Code begins----------------------------/*/

lli modpower(lli x, lli y, lli p)  
{  
    lli res=1;  
    x=x%p;
    if (x==0) return 0;
    while (y>0)  
    {  
        if (y&1)  
            res=(res*x)%p;  
        y=y>>1;  
        x=(x*x)%p;  
    }  
    return res;  
}
template <int32_t MOD>
struct mint {
        int32_t value;
        mint() : value() {}
        mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {}
        mint(int32_t value_, std::nullptr_t) : value(value_) {}
        explicit operator bool() const { return value; }
        inline mint<MOD> operator + (mint<MOD> other) const { return mint<MOD>(*this) += other; }
        inline mint<MOD> operator - (mint<MOD> other) const { return mint<MOD>(*this) -= other; }
        inline mint<MOD> operator * (mint<MOD> other) const { return mint<MOD>(*this) *= other; }
        inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
        inline mint<MOD> & operator -= (mint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
        inline mint<MOD> & operator *= (mint<MOD> other) { this->value = (uint_fast64_t)this->value * other.value % MOD; return *this; }
        inline mint<MOD> operator - () const { return mint<MOD>(this->value ? MOD - this->value : 0, nullptr); }
        inline bool operator == (mint<MOD> other) const { return value == other.value; }
        inline bool operator != (mint<MOD> other) const { return value != other.value; }
        inline mint<MOD> pow(uint64_t k) const { return mint<MOD>(modpower(value, k, MOD), nullptr); }
        inline mint<MOD> inv() const { return mint<MOD>(modpower(value, MOD-2, MOD), nullptr); }
        inline mint<MOD> operator / (mint<MOD> other) const { return *this * other.inv(); }
        inline mint<MOD> & operator /= (mint<MOD> other) { return *this *= other.inv(); }
};
template <int32_t MOD> mint<MOD> operator + (int64_t value, mint<MOD> n) { return mint<MOD>(value) + n; }
template <int32_t MOD> mint<MOD> operator - (int64_t value, mint<MOD> n) { return mint<MOD>(value) - n; }
template <int32_t MOD> mint<MOD> operator * (int64_t value, mint<MOD> n) { return mint<MOD>(value) * n; }
template <int32_t MOD> mint<MOD> operator / (int64_t value, mint<MOD> n) { return mint<MOD>(value) / n; }
template <int32_t MOD> std::istream & operator >> (std::istream & in, mint<MOD> & n) { int64_t value; in >> value; n = value; return in; }
template <int32_t MOD> std::ostream & operator << (std::ostream & out, mint<MOD> n) { return out << n.value; }
std::mt19937 gen(std::chrono::system_clock::now().time_since_epoch().count());
#define mnt mint<mod>

#define MAXN 5000005
lli spf[MAXN];
 
void sieve()
{
    spf[1] = 1;
    for (lli i = 2; i < MAXN; i++)
        spf[i] = i;
 
    for (lli i = 4; i < MAXN; i += 2)
        spf[i] = 2;
 
    for (lli i = 3; i * i < MAXN; i++) {
        if (spf[i] == i) {
            for (lli j = i * i; j < MAXN; j += i)
                if (spf[j] == j)
                    spf[j] = i;
        }
    }
}
 
mnt dp[5000005];

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	// auto start = std::chrono::high_resolution_clock::now();
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	sieve();
	lli t, l, r;
	cin>>t>>l>>r;
	
	dp[1]=0;

	mnt lst=1;
	mnt ans=0;

	ref(i,2,r)
	{
		dp[i] = i*(spf[i]-1)/2 + dp[i/spf[i]];

		if (l<=i && i<=r)
		{
			ans += lst * dp[i];
			lst *= t;
		}
	}

	cout<<ans<<endl;
 
	// auto stop = std::chrono::high_resolution_clock::now();
	// auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start);
	// #ifdef LOCAL
	// cerr << "\e[91mTime taken : " << ((long double)duration.count())/((long double) 1e9) <<"s\e[39m"<< endl;
	// #endif
 
	return 0;
}
 
// WA
// 1. overflow
// 2. re-initialize global variables for every test case.
// 3. edge cases like n=1
 
// Run time error
// 1. division by zero.
// 2. array bounds.
 
// TLE
// 1. move declarations outside