「SPOJ DIVCNT2」Counting Divisors (square)

题意

令 $\sigma_0(n)$ 表示 $n$ 的约数个数

求 $$\sum_{i=1}^n \sigma_0(i^2)$$

$n\le 10^{12}$

---

做法

Min_25筛板子题

丢链接跑

复杂度 $O(\frac{n^{\frac{3}{4}}}{\log n})$

---

代码

#include<cstdio>
#include<math.h>

using namespace std;
#define ll long long

const int N = 1000005;
int T, sn, id, cnt, prime[N];
ll n, g[N<<1], a[N<<1];
inline int Id(ll x){ return x<=sn?x:id-(n/x)+1;}
ll S(ll a, int b){
	if(a<prime[b]) return 0;
	ll ans=g[Id(a)]-(b-1)*3;
	for(int i=b, lim=sqrt(a); i<=cnt && prime[i]<=lim; ++i){
		ans+=S(a/prime[i], i+1)*3+5;
		for(ll x=(ll)prime[i]*prime[i], j=5; x*prime[i]<=a; x*=prime[i], j+=2)
			ans+=S(a/x, i+1)*j+j+2;
	}
	return ans;
}
int main() {
	scanf("%d", &T);
	while(T--){
		scanf("%lld", &n), sn=sqrt(n);
		cnt=id=0;
		for(ll i=1; i<=n; i=a[id]+1) a[++id]=n/(n/i), g[id]=(a[id]-1)*3;
		for(int i=2; i<=sn; ++i) if(g[i]!=g[i-1]){
			prime[++cnt]=i;
			ll lim=(ll)i*i;
			for(int j=id; a[j]>=lim; --j) g[j]-=g[Id(a[j]/i)]-(cnt-1)*3;
		}
		printf("%lld\n", S(n, 1)+1);
	}
	return 0;
}