因為n最大可能為10^12,遍歷n所有的因數確實很耗時
註意到好數僅由4或7組成,而n最大為12位
可換個思路,遍歷所有不大於n的好數,判斷是否有能被n整除的即可
而12位好數最多為2^12個,所以遍歷所有的好數會很快
這裏給出使用遞歸遍歷所有好數並判斷是否能被n整除的代碼,運行結果如下:
輸出符合樣例,望采納~
附源碼:
#include <stdio.h>
typedef long long ll;
int judge(ll cur, ll n) { // 遞歸判斷是否是真好數
if (cur > n)
return 0; // 不是真好數
if (cur > 0 && n % cur == 0)? // 有壹個好數因子即為真好數
return 1;
if (judge(cur * 10 + 4, n) == 1)
return 1;
return judge(cur * 10 + 7, n);
}
int main() {
int T;
ll n;
scanf("%d", &T);
while (T--) {
scanf("%lld", &n);
if (judge(0, n) == 1)
printf("YES\n");
else
printf("N0\n");
}
return 0;
}