M - Manasa爱数学 全排列函数 思维

Description

给你一个整数N，是否有它的排列可以被8整除？ 例如，如果数字N = 123，则{123，132，213，231，312，321}是可能的排列。 其中312可以被8整数，所以应该输出YES。

Input

第一行输入一个整数T，表示有T组数据。 接下来T行，每行输入一个整数N。 1 <= T <= 45 0 <= N <= 10^110

Output

对于每一组数据，如果其排列有一组可以被8整除，则输出YES，否则输出NO

Sample Input

2 61 75

Sample Output

YES NO

Hint

第一组数据：16是61的一组排列且可以整数8，所以输出YES。 第二组数据：75的两个排列57和75都不能整除8，所以输出NO。

题意

题解：

要注意1000/8=125 也就是说只用考虑后三位就可以的 当然这也不容易

AC代码

先放一个纯暴力全排列做法

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int main(){ int t; scanf("%d",&t); while (t--){ char st[120]; scanf("%s",st); int len =strlen(st); bool flag = false; sort(st,st+len); //字典序开始实现全排列 int sum; do{ sum = 0; for (int i = 0; i < len; ++i){ sum = sum*10+st[i]-'0'; } if (sum%8==0){ flag = true; break; } }while (next_permutation(st,st+len)); if (flag) puts("YES"); else puts("NO"); } return 0; }

最大时间复杂度 106 简单暴力

#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <set> #include <algorithm> using namespace std; int main(){ int t; scanf("%d",&t); char st[120]; int x1,x2,x3,x4,x5,x6; while (t--){ scanf("%s",st); int len = strlen(st); bool flag = false; if (len==1){ if (st[0]=='8'||st[0]=='0') flag = true; }else if (len == 2){ for (int i = 0; i < len; ++i){ for (int j = 0; j < len; ++j){ if (j!=i){ x1 = (st[i]-'0')*10+(st[j]-'0'); x2 = (st[j]-'0')*10+(st[i]-'0'); if (x1%8==0||x2%8==0){ flag = true; break; } } } if (flag) break; } }else { for (int i = 0; i < len; ++i){ for (int j = 0; j < len; ++j){ for (int k = 0; k < len; ++k){ if (i!=j&&j!=k&&i!=k){ x1 = (st[i]-'0')*100+(st[j]-'0')*10+(st[k]-'0'); x2 = (st[i]-'0')*100+(st[k]-'0')*10+(st[j]-'0'); x3 = (st[j]-'0')*100+(st[i]-'0')*10+(st[k]-'0'); x4 = (st[j]-'0')*100+(st[k]-'0')*10+(st[i]-'0'); x5 = (st[k]-'0')*100+(st[i]-'0')*10+(st[j]-'0'); x6 = (st[k]-'0')*100+(st[j]-'0')*10+(st[i]-'0'); if (x1%8==0||x2%8==0||x3%8==0||x4%8==0||x5%8==0||x6%8==0){ flag = true; break; } } } if (flag) break; } if (flag) break; } } if (flag) puts("YES"); else puts("NO"); } return 0; }