C# · 12月 20, 2021

给出长度为$n$的字符串,判断是否能删除一些数后被$8$整除

题意

给出长度为$n$的字符串,判断是否能删除一些数后被$8$整除

Sol

神仙题啊Orz

结论:

若数字的后三位能被$8$整除,则该数字能被$8$整除

证明

设$x = 10000 * a_i + 1000 * a_{i – 1} + dots$

发现大于$3$的位都会分解出$8$这个因数

然后大力枚举三个位置即可

/*

*/

#include

#include

#include

#include

#include

#include

#include

#include

#include

//#include

//#include

#define Pair pair

#define MP(x,y) make_pair(x,y)

#define fi first

#define se second

#define int long long

#define LL long long

#define ull unsigned long long

#define rg register

#define pt(x) printf(“%d “,x);

//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<22,stdin),p1 == p2) ? EOF : *p1++)

//char buf[(1 << 22)],*p1 = buf,*p2 = buf;

//char obuf[1<<24],*O = obuf;

//void print(int x) {if(x > 9) print(x / 10); *O++ = x % 10 + '0';}

//#define OS *O++ = ' ';

using namespace std;

//using namespace __gnu_pbds;

const int MAXN = 1e6 + 10,INF = 1e9 + 10,mod = 1e9 + 7;

const double eps = 1e-9;

inline int read() {

char c = getchar(); int x = 0,f = 1;

while(c '9') {if(c == '-') f = -1; c = getchar();}

while(c >= '0' && c <= '9') x = x * 10 + c – '0',c = getchar();

return x * f;

}

int N;

int a[MAXN];

char s[MAXN];

main() {

scanf(“%s”,s + 1);

N = strlen(s + 1);

for(int i = 1; i <= N; i++) a[i] = s[i] – '0';

for(int i = 1; i <= N; i++)

if(a[i] % 8 == 0) {printf(“YESn%d”,a[i]); return 0;}

for(int i = 1; i <= N; i++) {

for(int j = i + 1; j <= N; j++) {

int tmp = a[i] * 10 + a[j];

if(tmp % 8 == 0) {printf(“YESn%d”,tmp); return 0;}

}

}

for(int i = 1; i <= N; i++) {

for(int j = i + 1; j <= N; j++) {

for(int k = j + 1; k <= N; k++) {

int tmp = a[i] * 100 + a[j] * 10 + a[k];

if(tmp % 8 == 0) {printf(“YESn%d”,tmp); return 0;}

}

}

}

puts(“NO”);

return 0;

}

/*

2 2 1

1 1

2 1 1

*/