题目描述
设 S(N ) 表示 N 的各位数字之和，如 S(484) = 4+8+4 = 16， S(22) = 2+2 = 4。如果一个正整数满足 S(x*x) = S(x) *S(x)，我们称之为 Rabbit N umber。比方说，22 就是一个 Rabbit N umber，因为 S(484) = S(22) *S(22)。
现在，给出一个区间 [L, R]，求在该区间内的 Rabbit N umber 的个数。
输入输出格式
输入格式：
输入仅一行，为空格隔开的两个数 L 和 R。
输出格式：
输出仅一行一个整数，表示所求 Rabbit N umber 的个数。
输入输出样例
输入样例#1：
样例1：22 22
样例2：484 484
样例3：1 58
样例4：58 484
样例5：1000000000 1000000000
输出样例#1：
样例1：1
样例2：0
样例3：12
样例4：24
样例5：1
说明
1 <= L <= R <= 10^9
一看这道题 我就觉得是 道 数论题 然后 打表找规律 规律没找出来 然后想分块打表 最后写炸了
居然是数论题~~~~~~~~~
// 感谢来自二区 乡勇 的 题解 #include<cstdio> #include<algorithm> using namespace std; int l,r,ans; int s[20010],n; void find(int x,int y,int z){ long long a=x; a=a*a; int b=0; if(x>=l&&x<=r){ while(a){b+=a%10;a/=10;} if(y*y==b) s[++n]=x; } if(z>r) return; for(int i=0;i<4;i++) find(x*10+i,y+i,z*10); } int main(){ scanf("%d%d",&l,&r); find(0,0,1); sort(s+1,s+n+1); for(int i=1;i<=n;i++) if(s[i]!=s[i-1]) ans++; printf("%d ",ans); return 0; }