ZJNU 1244/1245

打表找规律吧……

一定要记得每一步都得开long long

然后可以发现所有的森哥数每一位只可能是0,1,2,3

就可以想到最高O(3^9)的算法

枚举1e9之内的所有满足条件的数判断

枚举9位数，最后1e9整无法枚举到

特判一下

#include<bits/stdc++.h>
using namespace std;
typedef long long L;
L senge(L in){
    L out=0;
    while(in)
        out+=in%10LL,in/=10LL;
    return out;
}
int main(){
    L t,m,l,r,a,b,c,d,e,f,g,h,i,s=0;
    scanf("%lld%lld",&l,&r);
    for(a=0;a<4;a++)
        for(b=0;b<4;b++)
            for(c=0;c<4;c++)
                for(d=0;d<4;d++)
                    for(e=0;e<4;e++)
                        for(f=0;f<4;f++)
                            for(g=0;g<4;g++)
                                for(h=0;h<4;h++)
                                    for(i=0;i<4;i++){
                                        t=a*1e8+b*1e7+c*1e6+d*1e5+e*1e4+f*1e3+g*100+h*10+i;
                                        if(t<l)
                                            continue;
                                        if(t>r){
                                            printf("%lld",s);
                                            return 0;
                                        }
                                        m=a+b+c+d+e+f+g+h+i;
                                        if(senge(t*t)==m*m)
                                            s++;
                                    }
    if(r==1e9)
        s++;
    printf("%lld",s);
    
    return 0;
}