水仙花数

一个三位数，各位数分别是 abc，则满足如下条件的数称为水仙花数：

\[abc = a^3 + b^3 + c^3 \]

比如：

\[153 = 1^3 + 5^3 + 3^3 \]

水仙花总数为153,370,371,407。

精确地说，3位数的三次幂数就叫做水仙数。数较多的还有其他相应称呼，如：

四个数字的四叶玫瑰数目共有3:1634,8208,9474；

5个五角星的数字有3:54748,927,93084；

六个数字的六个数字只有一个：548834；

七位北斗七星数共有4个：1741725,4210818,9800817,9926315；

八位的八仙数有3个：24678050,24678051,88593477。

程序：

#include <iostream>
#include <time.h>

void solve(int n);
int pow(int a, int n);
int get_sep_pow(int a, int n);

int main(int argc, char** argv) {
    clock_t start, end;
    // 找出3位到8位的满足条件的数
    for (int n = 3; n < 9; ++n) {
        start = clock();
        solve(n);
        end = clock();
        std::cout << "n = " << n << ", time cost: "
            << (end-start)*1000./CLOCKS_PER_SEC << " ms" << std::endl;
    }

    // 测试pow函数
    int m = 200;
    start = clock();
    for (int i = 0; i < 10000; ++i) {
        pow(6, m);
    }
    end = clock();
    std::cout << "test pow, time cost: "
        << (end-start)*1000./CLOCKS_PER_SEC << " ms" << std::endl;

    return 0;
}

void solve(int n) {
    int begin = pow(10, n-1);
    int end = pow(10, n) - 1;
    while (begin != end) {
        if (get_sep_pow(begin, n) == begin) {
            std::cout << begin << std::endl;
        }
        ++begin;
    }
}

int get_sep_pow(int a, int n) {
    int ret = 0;
    while (a) {
        ret += pow(a % 10, n);
        a = a / 10;
    }
    return ret;
}

// 未考虑n为负数的情况
int pow(int a, int n) {
    if (a < 2) {
        return a;
    }

    int ret = 1;
    int multi = 1;
    while (n) {
        ret *= n & 0x1 ? a : 1;
        n >>= 1;
        multi = n ? a*a : multi;
        a = multi;
    }
    return ret;
}

测试：

$ g++ -o narci_number narci_number.cpp && ./narci_number
153
370
371
407
n = 3, time cost: 0.079 ms
1634
8208
9474
n = 4, time cost: 0.463 ms
54748
92727
93084
n = 5, time cost: 3.968 ms
548834
n = 6, time cost: 45.888 ms
1741725
4210818
9800817
9926315
n = 7, time cost: 520.8 ms
24678050
24678051
88593477
n = 8, time cost: 7492.43 ms
test pow, time cost: 0.219 ms

526互联

水仙花数

水仙花数