HDOJ 1230(火星Ａ＋Ｂ)

火星A+B

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 7833    Accepted Submission(s): 2539

Problem Description 讀入兩個不超過25位的火星正整數A和B，計算A+B。需要注意的是：在火星上，整數不是單一進制的，第n位的進制就是第n個素數。例如：地球上的10進制數2，在火星上記為“1,0”，因為火星個位數是2進制的；地球上的10進制數38，在火星上記為“1,1,1,0”，因為火星個位數是2進制的，十位數是3進制的，百位數是5進制的，千位數是7進制的……  

Input 測試輸入包含若幹測試用例，每個測試用例占一行，包含兩個火星正整數A和B，火星整數的相鄰兩位數用逗号分隔，A和B之間有一個空格間隔。當A或B為0時輸入結束，相應的結果不要輸出。  

Output 對每個測試用例輸出1行，即火星表示法的A+B的值。  

Sample Input 1,0 2,1 4,2,0 1,2,0 1 10,6,4,2,1 0 0  

Sample Output 1,0,1 1,1,1,0 1,0,0,0,0,0

/*
  Name: 火星A+B 
  Copyright: 
  Author: 火星十一郎 
  Date: 25-07-25 08:14
  Description: 
*/
/*long long的十進制為20位*/
#include<stdio.h>
#include<string.h> 
#include<math.h>
/*
不必用素數定理也可估算出1到n的素數個數小于n/2
因為至少去掉所有 偶數,或者開平方 找到可能的最大素數 
*/
#define N 10000
int vis[N],prim[26],ans[30];//全局數組自動指派為0 
int k1,k2;
void is_prim()//不能與數組名同名 
{
	int m=(int)sqrt(N+0.5);
	int c=0,i,j;
	memset(vis,0,sizeof(vis));
	for(i=2;i<=m;i++)
	if(!vis[i])
	{
		prim[c++]=i;
		//printf("%d\n",prim[0]); 
		for(j=i*i;j<=N;j+=i)
			vis[j]=1;
	}
}
void add_output(int *temp1,int *temp2)
{
	int i,j;
	int len=k1>k2?k1:k2;
	memset(ans,0,sizeof(ans));
	//printf("%d\n",len);
	for(i=0,j=0;i<len;i++)
	{
		ans[i]+=temp1[i]+temp2[i];
		if(ans[j]>=prim[i]) 
		{
			ans[i+1]+= ans[i]/prim[i];
			ans[i]%=prim[i];
			//printf("%d\n",prim[i]);
			j++;
		}
		else
			j++;
	/*
	剛開始沒加else 
	代碼不對，因為若執行了if裡的j++；則有繼續執行了for循環體裡的j++ 
	*/
	}
	if(ans[len]!=0)
		len++;
	for(i=len-1;i>=1;i--)
		printf("%d,",ans[i]);
	printf("%d\n",ans[0]);
}	
int main()
{
    char str1[100],str2[100];
	int temp1[100]={0},temp2[100]={0};
    int i,j; int temp,len1,len2;
    is_prim();
    prim[0]=2;
    /*
    for(i=0;i<26;i++)
    	printf("%d ",prim[i]);
    printf("\n");
    /*測試後發現，N值太小（125） 
    改過後 prim[0]=1;
	是以必須加上prim[0]=2; 
	*/
    while(1)
    {
		memset(str1,0,sizeof(str1));
		memset(str2,0,sizeof(str2)); 
		memset(temp1,0,sizeof(temp1)); 
		memset(temp2,0,sizeof(temp2)); 
        scanf("%s %s",str1,str2);
        k1=k2=0;
        if(str1[0]=='0'&&str2[0]=='0')
            break;
        len1=strlen(str1);
        len2=strlen(str2);
        //為防止最後一個字元未被轉化為整形 
        str1[len1]=',';
		str2[len2]=',';  
		len1++;
		len2++; 
		 //轉化為整形 
        for(i=0,temp=0,k1=0;i<=len1;i++)
        {
			if(str1[i]==',')
			{
				temp1[k1++]=temp;
				temp=0;
				continue;
			}
			temp=temp*10+str1[i]-'0';
		}
		for(i=0,temp=0,k2=0;i<=len2;i++)
        {
			if(str2[i]==',')
			{
				temp2[k2++]=temp;
				temp=0;
				continue;
			}
			temp=temp*10+str2[i]-'0';
		}	
        //for(i=0;str1[i]!='\0';i++)
        //逆置 ,j<len1-1不能加等号，因為最後人為加了逗号 
        for(i=0,j=k1-1;j>=i;i++,j--)
        {   
      		temp=temp1[j];//temp需要時char 
            temp1[j]=temp1[i];
            temp1[i]=temp;
        }
      	for(i=0,j=k2-1;j>=i;i++,j--)//逆置 
        {   
      		temp=temp2[j];
            temp2[j]=temp2[i];
            temp2[i]=temp;
        }
		add_output(temp1,temp2);
	}
	return 0;
}
		
做這道題時，原來兩個temp沒清零，結果同一組資料，每次結果不一樣
看來，變量一定要賦初值，數組一定清空