Solution
\(\sum\limits_{i = 1}^n exlog(i) = exlog(n!) = \sum\limits_{1 \le p \le n,n 为质数} (f(p) \cdot \sum\limits_{j = 1}^\infty \left\lfloor\dfrac{n}{p^j}\right\rfloor)\).
需筛出所有 \(n\) 以内的质数，由于本题特殊的空间限制，我们不能直接使用线性筛。
正确的做法是，先筛出 \(\sqrt{n}\) 以内的质数，在将 \(1\) 至 \(n\) 分为 \(\sqrt{N}\) 个区间，使用区间筛质数即可。
Code
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define L(i, a, b) for(int i = (a); i <= (b); i ++ )
#define R(i, a, b) for(int i = (a); i >= (b); i -- )
using i64 = long long;
using u32 = unsigned int;
using pii = std::pair<int, int>;
const int maxn = 3e8 + 10;
const int maxp = 1.8e4 + 10;int N, A, B, C, D, l, r;
u32 ans = 0;
namespace sieve {bool st[maxp]; int Prime[maxp], P_cnt;void Euler(int _N) {L(i, 2, _N) {if(!st[i]) {st[i] = true;Prime[ ++ P_cnt] = i;}L(j, 1, P_cnt) {if(Prime[j] * i > _N) break;st[i * Prime[j]] = true;if(i % Prime[j] == 0) break;}} }
}namespace core {u32 f(u32 x) {return (u32)A * x * x * x + B * x * x + C * x + D;}u32 calc(u32 _N, u32 _P) {u32 res = 0;u32 tmp = _N;while(tmp >= _P) {tmp /= _P;res += tmp;}return res * f(_P);}void solve() {std::cin >> N >> A >> B >> C >> D;int Blen = (int)sqrt(N);sieve::Euler(Blen);L(i, 1, sieve::P_cnt) ans += calc(N, sieve::Prime[i]);int l = Blen + 1;while(l <= N) {r = std::min(l + Blen - 1, N);L(i, l, r) sieve::st[i - l + 1] = false;L(i, 1, sieve::P_cnt) L(j, (l + sieve::Prime[i] - 1) / sieve::Prime[i], r / sieve::Prime[i]) sieve::st[j * sieve::Prime[i] - l + 1] = true;L(i, l, r) if(!sieve::st[i - l + 1]) ans += calc(N, i);l = r + 1; }std::cout << ans << '\n';}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int tnum = 1;while(tnum -- ) core::solve();return 0;
}