1142:Smith Numbers

keyword

スミス数　素因数分解　C++

概要

n(<10^8)を越える最小のスミス数を求める問題。クエリは複数与えられる。
そんなに多くないだろうから埋め込みしようと思っていたけど全然終わらなかった。どうもスミス数は思っていたより密らしい。それならば探索する量は小さいので素直に実装する。

inline int digSum(int x){
    int ret = 0;
    for(;x;x/=10) ret += x%10;
    return ret;
}

int main(){
    int i, j, n;
    primeTable(50000);

    while(n = readint(), n){
        for(i=n+1;;i++){
            if(i<50001 && binary_search(ALL(ps),i)) continue;
            int sum = 0, x = i;
            j = 0;
            while(j < SZ(ps) && x > 1){
                if(!(x%ps[j])) sum += digSum(ps[j]), x /= ps[j];
                else j++;
            }
            if(x != i && digSum(i) == sum + ((x==1)?0:digSum(x))){
                printf("%d\n",i);
                break;
            }
        }
    }

    return 0;
}