朴素的杜教筛（不预处理小范围前缀和，只用哈希表记录一个数是否计算过）的复杂度真的是 $O(n^{\frac34})$ 吗。

写了三道杜教筛，没有朴素不 T 的。还是说整除分块的常数太大了，或者我杜教筛写法有问题。

本人写法

long long djs(long long n){
	if(n<=1)return n;
	if(vis[n])return sum[n];
	//vis 与 sum 为两个 unordered_map
	long long i,ed=1,res=(...);
	//(...) 处计算卷积和
	for(i=2;i<=n;i=ed+1){
		long long nx=n/(n/i);
		res-=(...)*djs(n/i)%mod-mod,res%=mod;
		//(...) 处 O(1) 计算 g 函数区间和。
		ed=nx;cnt++;
	}
	vis[n]=1;
	sum[n]=res;
	return res;
}