首页 > 代码库 > codeforces 490C. Hacking Cypher 解题报告
codeforces 490C. Hacking Cypher 解题报告
题目链接：http://codeforces.com/problemset/problem/490/C
题目意思：给出一个可能有10^6 位长的字符串且没有前导0的整数，问能否一分为二，使得前面的一部分被 a 整除 且 后面那部分被 b 整除，可以的话输出 “YES” 和 划分后的两部分，否则输出“NO”.
看到字符串这么长，一下子就吓怕了～～～用 mod 即可！这些要靠数学积累吧......
好常规的方法做——暴力枚举，当然不能遗漏啦，所以从左至右直到倒数第二个数字，都要算出mod a 的结果且保存到 vis[] 数组里面（vis初始化为-1）。然后从右往前直到顺数第二个数字，算出 mod b 的结果，当这个结果为0（即可以被b整除），且vis[前一位数字] = 0（表示前面的数可以被a整除），还有一个容易遗漏的一点，就是没有前导0（对应代码中的 s[i] != ‘0‘）那么就代表找到一个解。遍历完之后都没有的话就表示没有答案，输出“NO”
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 1e6 + 5; 8 int vis[maxn]; // 保存string中 0~len-1 个数字mod a 的结果 9 string s;10 11 int main()12 {13 #ifndef ONLINE_JUDGE14 freopen("in.txt", "r", stdin);15 #endif // ONLINE_JUDGE16 int a, b;17 while (cin >> s >> a >> b)18 {19 memset(vis, -1, sizeof(vis));20 int tmp = 0;21 int len = s.size();22 23 for (int i = 0; i < len-1; i++) // 至少要留一位给 b 嘛24 {25 tmp = (tmp * 10 + (s[i]-‘0‘)) % a; // 用到数学一些小知识26 vis[i] = tmp;27 }28 29 int base = 1;30 tmp = 0;31 for (int i = len-1; i > 0; i--) // 同理，a都要至少留一位数32 {33 tmp = ((s[i]-‘0‘) * base + tmp) % b;34 base = base * 10 % b;35 if (tmp == 0 && !vis[i-1] && s[i] != ‘0‘)36 {37 cout << "YES" << endl;38 cout << s.substr(0, i) << endl;39 cout << s.substr(i, len-i) << endl;40 return 0;41 }42 }43 cout << "NO" << endl;44 }45 return 0;46 }
codeforces 490C. Hacking Cypher 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。