题解：P2025 Dirichlet 半在线卷积

· · 题解

此题解非正解，复杂度 O(n\log n)，但是进行了有效的常数优化。

显然有一个非常简单的做法：先筛出来 \varphi(x)，然后从小到大枚举 i，枚举 ij=x，把 f_i 和 \varphi(j) 转移到 f_x 即可。由于因数数量是 O(n\log n)，所以这个复杂度也是 O(n\log n)。

不过如果真的就这么写，自然是过不去的。这里提供一个常数非常小的写法，似乎在这题数据范围下比正解还快很多。

先想想这个东西为什么会慢。算一算实际的转移次数，甚至都不到 10^9，而时限 4 秒，所以问题出在内存访问不够快。

首先考虑分块转移，也就是从小到大枚举 x\in [kB, (k+1)B)，然后对这个区间再枚举 ij=x 转移。这样我们扫描一个 200MB 的数组的次数减小了，就会快很多，大概只需要跑 3s。下面是一个参考实现，其中，计算除法的部分还用了一次整除分块：

constexpr int B = 2e6;
int n; cin>>n;
vector<u32> f(n+1), lst(n+1, 2);
f[1] = 1;
for(int l = 1, r = min(B, n); l <= n; l = r+1, r = min(l + B - 1, n)){
    for(u32 l0 = 1, r0, k; ; l0 = r0+1){
        k = r / l0, r0 = r / k;
        if(k == 1) break;
        rep(i,l0,r0){
            while(lst[i] <= k){
                f[i*lst[i]] += f[i] * phi[lst[i]];
                lst[i]++;
            }
        }
    }
}
u32 ans = 0;
rep(i,1,n){
    ans ^= f[i];
}
cout<< ans <<'\n';

不过就算这么搞，我们还是要多次扫描一遍 200MB 的数组，同时还需要在大概 8MB 的数组做随机访问，还能不能优化呢？

考虑一个非常简单的结论：设 ij=x，则 \min(i,j)\le \sqrt x。因此我们在分块后，区间转移的过程只需要枚举较小的那个因数就行了。

这么搞的话不需要多次扫 200MB 的数组，同时随机访问的内存也更密集。这样就跑得很快了，大概只需要 1.3s。同样给出参考实现：

constexpr int B = 65536
int n; cin>>n;
vector<u32> f(n+1);
f[1] = 1;

int l = 1, r = min(n, B);
rep(i,1,r/2){
    for(int j=2; j <= r/i; j++){
        f[j*i] += f[i] * phi[j];
    }
}
l = r+1, r = min(l + B - 1, n);
for(; l <= n; l = r+1, r = min(l + B - 1, n)){
    rep(j,l,r){
        f[j] += phi[j];
    }
    rep(i,2,B){
        rep(j, max(i, (l-1)/i+1), r/i){
            f[i*j] += f[i]*phi[j];
            if(i != j) f[i*j] += phi[i]*f[j];
        }
    }
}

u32 ans = 0;
rep(i,1,n){
    ans ^= f[i];
}
cout<< ans <<'\n';

在这题中，由于函数固定，我们还可以结合分段打表。

同时，上述解法的常数非常小。可以看出即使上面的参考实现仍有优化空间，这段代码仍然能在 P5495 取得优于一般 O(n\log\log n) 写法的前缀和的结果。

虽然复杂度更劣，但是由于好写好调常数小，暴力仍然是一个不错的选择。希望大家能够学会这种写法。