时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：5748
解决：1579
题目描述： 读入两个不超过25位的火星正整数A和B，计算A+B。需要注意的是：在火星上，整数不是单一进制的，第n位的进制就是第n个素数。例如：地球上的10进制数2，在火星上记为“1,0”，因为火星个位数是2进制的；地球上的10进制数38，在火星上记为“1,1,1,0”，因为火星个位数是2进制的，十位数是3进制的，百位数是5进制的，千位数是7进制的…… 输入： 测试输入包含若干测试用例，每个测试用例占一行，包含两个火星正整数A和B，火星整数的相邻两位数用逗号分隔，A和B之间有一个空格间隔。当A或B为0时输入结束，相应的结果不要输出。 输出： 对每个测试用例输出1行，即火星表示法的A+B的值。 样例输入： 1,0 2,1 4,2,0 1,2,0 1 10,6,4,2,1 0 0 样例输出： 1,0,1 1,1,1,0 1,0,0,0,0,0 来源：2006年浙江大学计算机及软件工程研究生机试真题
分析：
要细心。火星数38=“1，1，1，0”（由来：5*3*2*1 + 3*2*1 + 2*1 + 0*1，不过知道这个好像也没什么用），我是按位，以对应进制相加来求的
#include <stdio.h> #include <string.h> #define N 1000 void init(int prime[],int n){//素数筛选法 int i,j,primeSize; bool isPrime[N]; for(i=0;i<N;i++){ isPrime[i] = true; } primeSize = 0; for(i=2;i<N;i++){ if(!isPrime[i]){ continue; } if(primeSize < n){ prime[primeSize++] = i; }else{ break; } for(j=i*i;j<N;j+=i){ isPrime[j] = false; } } } int main(){ int prime[26]; init(prime,26); freopen("in.txt","r",stdin); int i,j,sizeA,sizeB,bufA[27],bufB[27];//bufA[]存火星数A,sizeA为bufA[]长度；bufB存火星数B char strA[100],strB[100];//一开始这里字符串数组设小了，导致runtime error好久。没考虑到双位数是2个字符，而错想成1个字符 while(scanf("%s%s",strA,strB) != EOF){ if((strlen(strA) == 1 && strA[0] == '0') || (strlen(strB) == 1 && strB[0] == '0')){ break; } sizeA = sizeB = 0; i = 0; while(strA[i] != '\0'){ int d = 1,sum = 0; char tmp[5]; j = 0; while(strA[i] != ',' && strA[i] != '\0'){ tmp[j++] = strA[i++]; } if(strA[i] == ','){ i++; } while(--j >= 0){ sum += (tmp[j]-'0')*d; d *= 10; } bufA[sizeA++] = sum; } i = 0; while(strB[i] != '\0'){ int d = 1,sum = 0; char tmp[5]; j = 0; while(strB[i] != ',' && strB[i] != '\0'){ tmp[j++] = strB[i++]; } if(strB[i] == ','){ i++; } while(--j >= 0){ sum += (tmp[j]-'0')*d; d *= 10; } bufB[sizeB++] = sum; } int ans[30],k; int tmpSum = 0,C = 0;//tmpSum为按位相加结果；C为进位 for(k=0,i=sizeA-1,j=sizeB-1;i>=0 && j>=0;i--,j--){ tmpSum = bufA[i] + bufB[j] + C; if(tmpSum < prime[k]){ C = 0; ans[k++] = tmpSum; }else{ C = 1; tmpSum -= prime[k]; ans[k++] = tmpSum; } } while(i >= 0){ tmpSum = bufA[i--] + C; if(tmpSum < prime[k]){ C = 0; ans[k++] = tmpSum; }else{ C = 1; tmpSum -= prime[k]; ans[k++] = tmpSum; } } while(j >= 0){ tmpSum = bufB[j--] + C; if(tmpSum < prime[k]){ C = 0; ans[k++] = tmpSum; }else{ C = 1; tmpSum -= prime[k]; ans[k++] = tmpSum; } } if(C == 1){//看最后是否还有进位 ans[k++] = 1; } for(i=k-1;i>0;i--){ printf("%d,",ans[i]); } printf("%d\n",ans[i]); } return 0; }
