第一份 TLE 最后三个点。好像是 n 比较大的时候, num 跑到后面会变成负数死循环。

int p[N];
inline void dfs(int dep,ll num,ll val)
{
//	printf("%lld %lld!\n",num,val);
	ans = (ans + val * Get_sum(n/num)%mod) %mod;
	for(int i=p[dep-1]+1; 1ll*num*prim[i]*prim[i]<=n && i<=cnt; ++i)
	{
		p[dep]=i;
		ll base=1ll*prim[i]*prim[i];
		for(int k=2; num*base<=n; ++k,base*=prim[i]) dfs(dep+1, num*base, val * (k-1)%mod * ((base*prim[i]%mod - base + mod) %mod) %mod);
	}
}

照着题解改成这样就好了。

void dfs(int dep,ll num,ll val)
{
	if(dep>cnt || 1ll*num*prim[dep]>n)
	{
		ans = (ans + 1ll*val * Get_sum(n/num)%mod) %mod;
		return;
	}
	ll base=1ll*prim[dep]*prim[dep];
	dfs(dep+1,num,val);
	for(int k=2; num*base<=n; base*=prim[dep],++k)
		dfs(dep+1, num*base, val * (k-1)%mod * base%mod * (prim[dep]-1)%mod);
}

深搜些不明白 /kel/kel/kel