算法
(数论、数的倍数) $O(10000)$
结论:8
的倍数的性质是其后三位是 $8$ 的倍数
- 若 $|s| = 1$,只需判断它是否等于 $8$ 即可
- 若 $|s| = 2$,判断它自身是否为 $8$ 的倍数,以及交换个位和十位的位置后是否为 $8$ 的倍数
- 若 $|s| \geqslant 3$,先统计一下 $s$ 中每个数字出现的次数 $cnt_i$,然后枚举 $0 \sim 999$ 中所有 $8$ 的倍数 $x$,同时统计 $x$ 中每个数字出现的次数 $nc_i$,并检验每个数字的 $nc_i$ 是否都不大于 $cnt_i$(如果存在 $s$ 的一种排列的后三位是 $8$ 的倍数,那么 $s$ 中每个数字出现的次数必然得大于等于构成某个 $8$ 的倍数的三位数的每个数字出现次数)。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::swap;
using std::string;
using std::vector;
bool solve(string s) {
if (s.size() == 1) {
return s == "8";
}
if (s.size() == 2) {
if (stoi(s) % 8 == 0) return true;
swap(s[0], s[1]);
if (stoi(s) % 8 == 0) return true;
return false;
}
vector<int> cnt(10);
for (char c : s) cnt[c - '0']++;
for (int i = 0; i < 1000; i += 8) {
int x = i;
vector<int> nc(10);
rep(j, 3) {
nc[x % 10]++;
x /= 10;
}
bool ok = true;
rep(j, 10) if (nc[j] > cnt[j]) ok = false;
if (ok) return true;
}
return false;
}
int main() {
string s;
cin >> s;
if (solve(s)) puts("Yes");
else puts("No");
return 0;
}