首先要有个 Observation，大概就是说可以发现对于每个质数的幂次 $a_i$，作为乘法系数是独立的。所以会有 $\text{exlog}_f(a\cdot b)=\text{exlog}_f(a)+\text{exlog}_f(b)$ 。但是这样直接筛的复杂度并不能过，空间会爆。然后考虑如何优化这一过程。
大概是说可以考虑每个质因数产生的贡献，彼此之间是**线性无关**的 ，所以可以分别考虑每个质数幂的贡献。具体的，我们只需要求出所有的质数以及质数的幂对答案的贡献就好了，这部分为了卡空间可以用埃氏筛。
但是发现还是过不去。因为埃氏筛的复杂度太高了。不过仔细分析一波，发现慢在诸如 $2,3,5,7$ 这种比较小的质因子 $p$，会进行 $\left\lfloor\dfrac{n}{p}\right\rfloor$ 次筛除操作。于是可以先暴力跑出 $2,3,5,7$ 的贡献，然后算其他的时就可以不考虑这些数了。
但是发现这样空间还是会有点问题。于是可以用 `bitset ` + 合并状态来压缩。合并状态的原理是刨除了所有 $2,3$ 的倍数之后，空间就可以只开 $\dfrac{1}{3}$ 。
个人觉得这题能放到 F，唯一的原因就是因为需要十分优秀的卡常 and 卡空间技术。
```cpp
#include <bitset>
#include <cstdio>
const int N = 100000005 ;
using std :: bitset ;
typedef long long ll ;
typedef unsigned int lint ;
int n ;
bitset <N> vis ;
int A, B, C, D ;
lint ans ;
inline bool chk(int x){
return ((!(x & 1)) || (x % 3 == 0) || (x % 5 == 0)) ;
}
lint calc(int p){
return 1u * A * p * p * p + 1u * B * p * p + 1u * C * p + D ;
}
lint solve(int p){
lint ret = 0, v = calc(p) ;
for (ll x = p ; x <= n ; x *= p)
ret += 1u * (n / x) * v ; return ret ;
}
int main(){
scanf("%d", &n) ; ans = 0 ;
scanf("%d%d%d%d", &A, &B, &C, &D) ;
if (n >= 2) ans += solve(2) ;
if (n >= 3) ans += solve(3) ;
if (n >= 5) ans += solve(5) ;
for (int i = 7 ; i <= n ; ++ i){
if (chk(i)) continue ;
if (vis[i / 3]) continue ; ans += solve(i) ; //printf("%u\n", ans) ;
for (int j = i + i ; j <= n ; j += i)
if (!chk(j)) vis[j / 3] = 1 ;
}
printf("%u\n", ans) ; return 0 ;
}
```