注意到 S(i)∈[1,90]S(i)\in[1,90]S(i)∈[1,90]，这是一个很小的值域限制，可以考虑枚举。 Ans=∑i=1n[n mod i=S(i)]=∑d=190∑i=1n[S(i)=d][n−i⌊ni⌋=d]=∑d=190∑i∣(n−d)∧i⌊ni⌋=n−d[S(i)=d]\begin{aligned} Ans&=\sum_{i=1}^n[n \bmod i=S(i)] \\ &=\sum_{d=1}^{90}\sum_{i=1}^n[S(i)=d][n-i\lfloor\frac ni\rfloor=d] \\ &=\sum_{d=1}^{90}\sum_{i \mid (n-d)\wedge i\lfloor\frac ni\rfloor=n-d}[S(i)=d] \\ \end{aligned} Ans =i=1∑n [nmodi=S(i)]=d=1∑90 i=1∑n [S(i)=d][n−i⌊in ⌋=d]=d=1∑90 i∣(n−d)∧i⌊in ⌋=n−d∑ [S(i)=d] 枚举因数即可，时间复杂度 O(Tnlog⁡n)O(T\sqrt n\log n)O(Tn logn)。