A water problem

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 97    Accepted Submission(s): 58 Problem Description Two planets named Haha and Xixi in the universe and they were created with the universe beginning. There is 73 days in Xixi a year and 137 days in Haha a year. Now you know the days N after Big Bang, you need to answer whether it is the first day in a year about the two planets.   Input There are several test cases(about 5 huge test cases). For each test, we have a line with an only integer N(0≤N) , the length of N is up to 10000000 .   Output For the i-th test case, output Case #i: , then output "YES" or "NO" for the answer.   Sample Input 10001 0 333   Sample Output Case #1: YES Case #2: YES Case #3: NO   Author UESTC   Source 2016中国大学生程序设计竞赛 - 网络选拔赛   真是被这个题目恶心到了， 其实也怪自己见识的太少，用了很长的时间的高精度，最后用高精度加法过了，最后一问同学，简直是个水题！ 都说一下吧，哎~~~ 因为是一个大数取模吗，既是73的倍数，又是137的倍数，所以73*137 = 10001，所以可以枚举每一个数字，边枚举边取模，这样还哪能用到高精度啊，， 就像转换成10进制一样v = （v * 10 + a ) % mod，这样如果最后v是0 就yes了，否则就no！ 高精度思路： 可能是找的板子有问题，全部都是超时，爆内存， 转换一下，把10001  = 10000 + 1 这就相当于输入n ，找出一个k 满足 k*10000 + k = n，这就相当于两个错位加法运算，直接模拟加法就行了！ 奇怪的是，JAVA交好像没有过的~全都是爆内存！ 水题代码： #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 10000000 + 1; const int mod = 10001; char s[maxn]; int main(){ int kase = 0; while(scanf("%s",s) == 1){ int len = strlen(s); int v = 0; for (int i = 0; i < len; ++i){ v = (v*10 + s[i]-48) % mod; } if (v == 0)printf("Case #%d: YES\n",++kase); else printf("Case #%d: NO\n",++kase); } return 0; } /* 55894144405555 */ 找抽代码： #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 10000000 + 1; char s[maxn]; char a[maxn]; char b[maxn]; char ans[maxn]; int main(){ int kase = 0 ; while(scanf("%s",s+1) == 1){ int len = strlen(s+1); if (len > 4){ a[len] = s[len]-48; a[len-1] = s[len-1]-48; a[len-2] = s[len-2]-48; a[len-3] = s[len-3]-48; int flag = 0; for (int i = 1; i <= len-4; ++i){ int shang = a[len-i+1]; int xia = s[len-4-i+1]-48; if (xia >= flag + shang)a[len-4-i+1] = xia - shang - flag,flag = 0; else a[len-4-i+1] = xia+10-flag-shang,flag = 1; } a[len+1] = a[len+2] = a[len+3] = a[len+4] = 0; bool ok =true; int cnt = 0; for (int i = 1; i <= len; ++i)a[i] = a[i+4]; // for (int i = 1; i <= len; ++i)printf("%d ",a[i]); // puts(""); // for (int i = 1; i <= len; ++i)printf("%d ",a[i]); // puts(""); b[1] = b[2] = b[3] = b[4] = 0; for (int i =5; i <= len; ++i)b[i] = a[i-4]; // for (int i = 1; i <= len; ++i)printf("%d ",b[i]); // puts(""); flag = 0; for (int i = len ;i >= 1; --i){ int t = a[i] + b[i] + flag; if (t > 9)flag = 1,t %= 10; else flag = 0; ans[i] = t; } // for (int i = 1; i <= len ;++i)printf("%d ",ans[i]); for (int i = 1; i <= len; ++i){ if (s[i]-48 != ans[i]){ ok = false; break; } } if (ok)printf("Case #%d: YES\n",++kase); else printf("Case #%d: NO\n",++kase); }else { int v = 0 ; for (int i = 1; i <= len; ++i){ v = v * 10 + s[i] - 48; } if (v % 10001 == 0)printf("Case #%d: YES\n",++kase); else printf("Case #%d: NO\n",++kase); } } return 0; } /* 55894144405555 */