大致题意
给定一个长度不超过 \(10^5\) 的数字 \(n\)。
选择它的一个数字 \(x\) 将它变为 \(x^2\) ( \(x^2 \le 9\) )。
通过任意次操作，是否可能获得一个能被 \(9\) 整除的数字？
解法
因为 \(x^2 \le 9\)，所以 \(x \le 3\),但是 \(0^2\) 为 \(0\), \(1^2\) 为 \(1\)。所以，所选的 \(x\) 应从 \(2\)、 \(3\) 中选择。且 \(2^2\) 为 \(4\), \(3^3\) 为 \(9\)。对于 \(2\)， 每次只会增加 \(2\)，每 \(9\) 次为 \(9\) 的倍数。对于 \(3\)，每次只会增加 \(6\)，每 \(3\) 次为 \(9\) 的倍数，所以 \(3\) 最多选 \(2\) 个，不然没有意义。所以，我们可以考虑去枚举选 \(2\) 和选 \(3\) 的个数，因为 \(2\) 至多选 \(8\) 个， \(3\) 至多选 \(2\) 个，所以枚举的时间复杂度为一个小常数，不超过 \(27\)。判断是否是 \(9\) 的倍数只需判断位数和是否为 \(9\) 的倍数。所以代码的总时间复杂度为 \(O(n)\)。如果存在可行的情况输出 YES 否则输出 NO。
提示：记得枚举不选的情况！
接下来是代码环节：
#include<bits/stdc++.h>
using namespace std;
int t, a[20];
string s;
signed main() {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> t;while (t --) {memset(a, 0, sizeof(a));cin >> s;int len = s.size();s = " " + s;int sum = 0;for (int i = 1; i <= len; i ++) {sum += s[i] - '0';a[s[i] - '0'] ++;}if (sum % 9 == 0) {cout << "YES\n";continue;}bool flag = false;for (int i = 0; i <= min(8, a[2]); i ++) {if ((sum + i * 2) % 9 == 0) {cout << "YES\n";flag = true;break;}for (int j = 0; j <= min(2, a[3]); j ++) {if ((sum + i * 2 + j * 6) % 9 == 0) {cout << "YES\n";flag = true;break;}}if (flag) {break;}}if (!flag) {cout << "NO\n";}}return 0;
}