学步园

    做这道浙大的考研上机题时，以为要转换成long long型再相加。这个思路为这道题贡献了好几次WA。

    洗澡的时候才灵光一现，有了新的想法，就是一道长整数加法嘛，只不过不是十进制的罢了，而且各个位的权值都不一样，算是见识的长整数加法的极致版本了。

    题目URL:http://ac.jobdu.com/problem.php?id=1016

    我的AC代码：

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

const int Max = 25 + 5;
int prime[1000];
int arra[Max], arrb[Max], arrc[Max];
int lenA, lenB;

int split(int s[], string &str)
{
	int p(0);
	string::size_type pos = 0, comma;

	while((comma = str.find(',', pos)) != string::npos)
	{
		s[p++] = (atoi(str.substr(pos, comma - pos).c_str()));
		pos = comma + 1;
	}
	s[p++] = (atoi(str.substr(pos).c_str()));
	return p;
}

void getPrime()
{
	bool pri;
	int index = 0;

	for(int i=2; i<=1000; i++)
	{
		int m = sqrt((double)i);
		
		pri = true;
		for(int j=2; j<=m; ++j)
			if(i % j == 0)
			{
				pri = false;
				break;
			}

		if(pri) prime[index++] = i;
	}
}

void inverse(int a[], int len)
{
	for(int i=0; i<len/2; ++i) swap(a[i], a[len-1 - i]);
}

void add(int a[], int b[], int c[])
{
	int carry(0);

	for(int i(0); i<Max; ++i)
	{
		c[i] = a[i] + b[i] + carry;
		carry = c[i] / prime[i];
		c[i] %= prime[i];
	}
}

int main()
{
	string a, b;
	int start;

	getPrime();
	while(cin >> a >> b && !(a == "0" || b == "0"))
	{
		memset(arra, 0, sizeof(arra));
		memset(arrb, 0, sizeof(arrb));
		memset(arrc, 0, sizeof(arrc));

		lenA = split(arra, a), lenB = split(arrb, b);
		inverse(arra, lenA), inverse(arrb, lenB);
		add(arra, arrb, arrc);
		
		start = Max;
		while(!arrc[--start] && start);
		for(int i(start); i>=0; --i)
			if(i) cout << arrc[i] << ',';
			else cout << arrc[i];
		cout << endl;
	}
	system("pause");
	return 0;
}