我们用积分证明在预处理出 $1-n^\frac 2 3$ 的函数值的情况下，杜教筛的复杂度是 $O(n^\frac 2 3)$。
在证明过程中和 map 优化没有任何关系，因此我把它理解成了常数优化。
然而，我去掉了 map 优化之后，却发现直接 T 飞了。
同一份代码 有 map 优化 和 去掉 map 优化。
为此，我在本地用下面的代码进行测试：

int o=0;
ll getmu(int n){
	if(n<=w) return sum[n];
	if(mp.count(n)) return mp[n];
	ll ans=1;
	for(ll l=2,r;l<=n;l=r+1){
		++o;//统计循环次数
		r=n/(n/l);
		ans-=(r-l+1)*getmu(n/l);
	}
	mp[n]=ans;
	return ans;
}

为了尽可能减少常数因子的干扰，我只使用一组 $n=10^9$ 的数据，并且去掉了计算 $\varphi$ 函数的部分，主函数中只调用一次 getmu(n)。 测试结果如下：

input:
1
1000000000

有 map:0.938s tim=3904151
无 map:4.258s tim=136360124 

完整测试代码
有 map 时的表示大致符合 $n^\frac 2 3=10^6$ 的期，而没有 map 时，代码的效率几乎已经退化到线性级别了。
蒟蒻不解...求大佬解答，感谢！