_a_mathematics_problem.cpp

#include <iostream>
#include <vector>
#include <algorithm>
//#include <unordered_map>
using namespace std;
const int MAXX = 100000;
const int MAXXSQ = 1000;
long long mod = 1000000007;
vector <int> primes = {2};
vector <bool> isprime (MAXX, true);
void sieve () {
    int i = 2, j, i2;
    for (j =  4; j < MAXX; j += i)
        isprime [j] = false;
    for (i = 3; i < MAXXSQ; i += 2) {
        if (isprime[i]) {
            for (j =  i * i; j < MAXX; j += i)
                isprime [j] = false;
            primes.push_back(i);
        }
    }
    // i is 1001, which is multiple of 6   - 1
    for (; i < MAXX - 2; i += 6) {
        if (isprime [i]) primes.push_back (i);
        i2 = i + 2;
        if (isprime [i2]) primes.push_back (i2);
    }
}
long long square (long long a) { return a*a; }
// not faster with map in c++
//unordered_map <long long, long long> sum1d;
//unordered_map <long long, long long> :: iterator it;
long long sum1 (long long n)
{
    if (n == 0) return 0;
    //it = sum1d.find (n);
    //if (it != sum1d.end ()) return it -> second;
    //sum1d [n] = square ((n + 1) / 2) + sum1(n / 2);
    //return sum1d [n];
    return square ((n + 1) / 2) + sum1(n / 2);
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    long long t, P, Q, N, p, n, ans, sum, pi, qi;
    cin >> t;
    sieve();
    while (t--) {
        cin >> P >> Q >> N;
        ans = 0;
        pi = lower_bound (primes.begin (), primes.end (), P) - primes.begin ();
        qi = upper_bound (primes.begin (), primes.end (), Q) - primes.begin ();
        for (int i = pi; i < qi; i++) {
            p = primes [i];
            n = N;
            while (n){
                sum = n * (n + 1) / 2 - 2 * sum1 (n);
                sum = (sum + mod) % mod;
                ans += (p - 1) * sum % mod;
                ans = (ans + mod) % mod;
                n /= p;
            }
        }
        cout << ans << '\n';
    }
 return 0;
}