#C241001A. 简单数论

标签（Label）

• 数学推理
• 观察+分析

网址（Website）

题目详情 - 简单数论 - Super

题解 - 简单数论 - Super

题解（Solution）

$\qquad$发现 $S(m)$ 只有 $99$ 个，直接暴力枚举，发现 $O(99T\sqrt N)$ 枚举因数容易超时，考虑先枚举因数，然后查找在 $[\max(1,n-108),n]$ 中可能的 $s$ 的数量即可。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;
bool ST;

int n,ans;
inline int cal(int x){
	int res = 0;
	while(x){
		res += x%10;
		x/=10;
	}return res;
}

inline int solve(){
	int l = max(1ll,n-108);
	int r = n;
	for(int i=1;i*i<=n;i++){
		int b = (l-1)/i+1;//i的最小枚举倍数
		while(b*i<=r){
			int s = n-b*i;
			if(cal(b) == s && b>s) ans++;
			if(cal(i) == s && i>s && i!=b) ans++;
			b++;
		}
	}return ans;
} 

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	int T = rd(), Tim = clock();
	while(T--){
		n = rd(), ans = 0;	
		printf("%lld\n",solve());
	}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}