在此输入标题

注意到 $S(i)\in[1,90]$，这是一个很小的值域限制，可以考虑枚举。

$$\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}$$

枚举因数即可，时间复杂度 $O(T\sqrt n\log n)$。

#include <bits/stdc++.h>
using namespace std;

#define chmax(a,b) ((a)=max((a),(b)))
#define chmin(a,b) ((a)=min((a),(b)))
typedef long long ll;

ll T,n;

int S(ll x){
	int ans=0;
	while(x)ans+=x%10,x/=10;
	return ans;
}

int main(){
	cin>>T;
	while(T--){
		cin>>n;
		ll ans=0;
		for(int d=1;d<=90;d++){
			ll m=n-d;
			for(ll i=1;i*i<=m;i++){
				if(m%i==0){
					if(n%i==d&&S(i)==d)ans++;
					if(i*i!=m){
						if(n%(m/i)==d&&S(m/i)==d)ans++;
					}
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}