能否被8整除

题目：给定一个非负整数，问能否重排它的全部数字，使得重排后的数能被8整除。输入格式：多组数据，每组数据是一个非负整数。非负整数的位数不超过10000位。输出格式每组数据输出一行,YES或者NO，表示能否重排它的全部数字得到能被8整除的数。注意：重排可以让0开头。

思路

考虑到64位整型可以直接取余8求得结果，所以当输入非负整数位数小于20位的时候，可以直接转换成64位整型进行计算。
对于一个非负整数，最后四位相当于是 p1000 + x100 + y10 + z ，可以很显然的看出p1000必然能被8整除，所以一个非负整数只需要后三位能被8整除，那么这个数就一定能被8整除。所以如果我们能从这个数中任意取出三位，作为最后三位，其值能被8整除，就输出YES，否则NO。
没必要对可能的10000位做全排列，因为0-9每个数最多只能用3次，我们只需要遍历一遍每一位，将0-9出现的次数记录下来，最多允许记录3次。这样最坏的情况下需要对30个数进行全排列即可，效率会非常高。

代码

#include <stdio.h>
#include <string.h>
#include <sys/types.h>

#define MAX 10001

int has_num[10];    //0-9在这个数中出现的次数

bool check()
{
    int deal_num[30];   //0-9每个数最多可以用3次，只需要30的空间
    int n = 0;
    //将所有出现过数依次存放在deal_num数组中
    for (int i=0; i<10; i++) {
        for (int j=0; j<has_num[i]; j++) {
            deal_num[n] = i;
            n++;
        }
    }

    //排列任意三个数组成一个整数，其值能被8整除，返回true，否则false
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (j == i)
                continue;
            for (int k=0; k<n; k++) {
                if (k == i || k == j) {
                    continue;
                }
                if ((deal_num[i]*100 + deal_num[j]*10 + deal_num[k]) % 8 == 0)
                    return true;
            }
        }
    }
    return false;
}

int main()
{
    char str_num[MAX];  //用于保存不超过10000位的整数
    int n;
    long long temp = 0; //如果位数小于等于19，直接转换为64位整型

    for (;;) {
        memset(str_num, 0, sizeof(str_num));
        for (int i=0; i<10; i++) {
            has_num[i] = 0;
        }
        if (scanf("%s", &str_num) == 1) {
            n = strlen(str_num);
            //转换为64位整型
            if (n <= 19) {
                sscanf(str_num, "%lld", &temp);
                if ((temp % 8) == 0)
                    printf("YES\n");
                else
                    printf("NO\n");
                continue;
            }
            
            //将0-9出现的次数保存在has_num数组中，最多3次
            for (int i=0; i<n; i++) {
                if (has_num[(int)str_num[i] - 48] < 3)
                    has_num[(int)str_num[i] - 48]++;
            }
            if (check())
                printf("YES\n");
            else
                printf("NO\n");
            continue;

        } else {
            break;
        }
    }
    return 0;
}