Codeforces 490C Hacking Cypher(暴力)

2019-04-13 20:52发布

站内文章 / 模拟电子
17334 0 1685
题目链接：Codeforces 490C Hacking Cypher 分成的两个数字不能有前导0，用复杂度为o(n)的递推方法处理出每个前缀模A，后缀模B的值，找到位置对应前后缀模A、B所得值均为0。 #include #include #include using namespace std; const int maxn = 1e6 + 5; int N, A, B, l[maxn], r[maxn], t[maxn]; char s[maxn]; int solve () { t[0] = 1; for (int i = 1; i <= N; i++) t[i] = t[i-1] * 10 % B; for (int i = 0; i < N; i++) l[i] = (l[i-1] * 10 + (s[i] - '0')) % A; int tmp = 0; for (int i = N - 1; i; i--) { tmp = (tmp + (s[i] - '0') * t[N-i-1]) % B; if (s[i] == '0') continue; if (tmp == 0 && l[i-1] == 0) return i; } return 0; } int main () { scanf("%s%d%d", s, &A, &B); N = strlen(s); int ans = solve(); if (ans) { printf("YES "); for (int i = 0; i < ans; i++) printf("%c", s[i]); printf(" "); for (int i = ans; i < N; i++) printf("%c", s[i]); printf(" "); } else printf("NO "); return 0; }

热门文章