「不知道该说什么题」[Codeforces 1017F] The Neutral Zone

· · 题解

首先要有个 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 卡空间技术。

#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 ;
}