记录编号	343155	评测结果	AAAAAAAAAA
题目名称	Rabbit Number	最终得分	100
用户昵称	JVendetta	是否通过	通过
代码语言	C++	运行时间	3.544 s
提交时间	2016-11-08 22:03:57	内存使用	68.95 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> 
#define N 10000010 
#define ll long long
#define INF 1000000000
using namespace std;
ll a[N],len,old;
ll fun(ll x){
	x*=x;
	ll ans=0;
	while(x){
		ans+=x%10;
		x/=10;
	}
	return ans;
}
void dfs(ll x,ll now){
	if(now>INF) return ;
	int i;
	if(now!=0)
		dfs(x,now*10);
	if(x==0){
		if(fun(now)==old)
			len++,a[len]=now;
		return ; 
	}
	if(x>=10){
		for(i=x-9;i<=9;i++)
			dfs(x-i,now*10+i);
		for(i=1;i<x-9;i++)
			dfs(x-i,now*10+i);
	}
	else{
		for(i=1;i<=x;i++)
			dfs(x-i,now*10+i);
	}
	return ;
}
int main(){
	freopen("rabbits.in","r",stdin);
	freopen("rabbits.out","w",stdout);
	int l,r,i,ans=0;
	for(i=1;i<=12;i++)
		old=i*i,dfs((ll)i,0);
	sort(a+1,a+1+len);
	scanf("%d%d",&l,&r);
	for(i=1;i<=len;i++){
		if(a[i]>=l && a[i]<=r)
			ans++;
		else if(a[i]>r) break;
	}
	printf("%d\n",ans);
}