我遇到了一个递推的式子：

其中 $g_1 = 1$

我利用的类似数论分块的方式，并加上了记忆化：

using lint = long long;
lint calc(lint x) {
	if (g.get(x))
		return g.get(x);
	if (x == 1) return 1;
	
	lint v = 0;
	for (lint i = 1; i * i <= x; ++i) {
		lint r = min(x + 1, (i + 1) * (i + 1));
		v += calc(i) * (r - i * i) % mod;
		v %= mod;
	}
	
	g.set(x, v);
	return v;
}

我很好奇其复杂度到底是怎么样的……因为 1e9 可以很轻松的跑过。