【枚举】Petrozavodsk Summer Training Camp 2016 Day 6: Warsaw U Contest, XVI Open Cup Onsite, Sunday, August 28, 2016 Problem G. Equation

f(n)定义为n的十进制表示下所有位的平方和。

问你方程K*f(n)=n在a<=n<=b中的解的个数。

发现f(n)最大不超过2000，可以直接枚举f(n)，然后判断K*f(n)的位的平方和是否恰好为f(n)。

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
ll K,a,b;
int main(){
//freopen("g.in","r",stdin);
int ans1=0,ans2=0;
cin>>K>>a>>b;
for(ll fn=1;fn<=2000ll;++fn){
if(fn>(a-1ll)/K){
break;
}
ll N=fn*K;
ll t=0;
while(N){
t+=(N%10ll)*(N%10ll);
N/=10ll;
}
if(t==fn){
++ans1;
}
}
for(ll fn=1;fn<=2000ll;++fn){
if(fn>b/K){
break;
}
ll N=fn*K;
ll t=0;
while(N){
t+=(N%10ll)*(N%10ll);
N/=10ll;
}
if(t==fn){
++ans2;
}
}
printf("%d\n",ans2-ans1);
return 0;
}