dream.cpp

#include <ametus.h>

MI cin;

typedef uint32_t ui;
typedef uint64_t ul;

const int L = 4641589;
const int $p = L;
const ui mod = 998244353;

ui pr[$p + 1], phi[L + 1];
bool co[L + 1];
inline ui add(ui x, ui y) { return (x += y) >= mod? x - mod: x; }
inline void Add(ui &x, ui y) { if ((x += y) >= mod) x -= mod; }
inline ui sub(ui x, ui y) { return x - y + (x < y? mod: 0); }
inline void Sub(ui &x, ui y) { if (x < y) x += mod; x -= y; }
inline ui div2(ui x) { return ((x & 1)? x + mod: x) >> 1; }
inline ul ksm(ul x, ul p = mod - 2) { ul r = 1; for (; p; p >>= 1, (x *= x) %= mod) if (p & 1) (r *= x) %= mod; return r; }
inline ui s2(ul n) { return sub(ksm(2, n + 1), 2); }
inline void sieve() {
    phi[1] = 1;
    E(i, 2, L) {
        if (!co[i]) { pr[++pr[0]] = i; phi[i] = i - 1; }
        E(j, pr[0]) {
            let k = pr[j] * i; if (k > L) break;
            co[k] = 1;
            if (i % pr[j]) phi[k] = (ul)phi[i] * (pr[j] - 1) % mod;
            else { phi[k] = (ul)phi[i] * pr[j] % mod; break; }
        }
        Add(phi[i], phi[i - 1]);
    }
}
struct {
    ul N; ui mem[2500];
    static inline ul g_sum(ul n) { return n % mod; }
    static inline ul fg_sum(ul n) { n %= mod; return n * (n + 1) / 2 % mod; }
    inline void init(ul n) {
        N = n;
        memset(mem, -1, sizeof(mem));
    }
    inline ui operator()(ul n) {
        if (n <= L) return phi[n];
        ui &res = mem[N / n];
        if (~res) return res;
        ui sum = 0, lst = 1;
        for (ul l = 2, r; l <= n; l = r + 1) {
            let t = n / l; r = n / t; let cur = g_sum(r);
            sum = (sum + (ul)sub(cur, lst) * operator()(t)) % mod;
            lst = cur;
        }
        return res = sub(fg_sum(n), sum);
    }
} phi_sum;
inline ui F(ul n) {
    ui ans = phi_sum(n); ul s = 0;
    while (n >>= 1) s += phi_sum(n);
    return sub(ans, s % mod);
}
inline ui solve(ul n) {
    if (!n) return 0;
    phi_sum.init(n);
    ui ans = s2(n), lst = 0;
    for (ul l = 1, r; l <= n; l = r + 1) {
        let d = n / l; let cur = s2(r = n / d);
        ans = (ans + (ul)sub(cur, lst) * F(d)) % mod;
        lst = cur;
    }
    return div2(ans);
}
int main() {
    sieve(); ul l, r; cin > l > r;
    cout < sub(solve(r), solve(l - 1)) < endl;
}