记录编号	343447	评测结果	AAAAAAAAAA
题目名称	Rabbit Number	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	2.483 s
提交时间	2016-11-09 10:58:12	内存使用	0.29 MiB

#include<cstdio>
#include<algorithm>
#define file(x) "rabbits."#x
typedef long long ll;
int l,r,now[30];
int gsum(ll x){
	int s=0;
	while(x) s += x%10,x /= 10;
	return s;
}
ll comb(int* a,int len){
	ll s = 0;
	for (int i = 0;i < len;i++) s = s*10 + a[i];
	return s;
}
ll lim,lcnt,ret;
void dfs(int cnt){
	if (cnt==lcnt) {
		ll nx = comb(now,cnt);
		if(nx <= lim) {
			int sig = gsum(nx);
			ret += sig*sig == gsum(nx*nx);
		}
		return ;
	}
	for (int i = 0;i < 4;i++) now[cnt] = i,dfs(cnt + 1);
}
int calc(int nlim) {
	lim=nlim;
	ret=lcnt=0;
	while(nlim) nlim/=10,lcnt++;
	dfs(0);
	return ret;
}
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	scanf("%d%d",&l,&r);
	printf("%d",calc(r) - calc(l-1));
}