SPOJ 74. Divisor Summation 分解数字的因子

本题有两个难点：

1 大量的数据输入，没处理好就超时 - 这里使用buffer解决

2 因子分解的算法 a）暴力法超时 b）使用sieve（筛子），不过其中的算法逻辑也挺不容易搞对的。

数值N因子分解逻辑：

1 保存所有可以sqrt(N)范围内的质素

2 找到可以被N除尽的质素d， 然后用d去除N，使用deg变量，保存度，即有多少个d可以被N除尽

3 用d去乘所有已经找到的因子（包括1），如果度deg大于1，那么循环i从1到deg， 用d*i去乘所有找到的因子

找到所有因子相加，减去N，就是答案。

原题：http://www.spoj.com/problems/DIVSUM/

class DivisorSummation47
{
	const static int MAX_BUF = 5120;
	int st, len;
	char inBuf[MAX_BUF];

	const static int FLASH_P = MAX_BUF - 12;
	int oSt;
	char outBuf[MAX_BUF];

	const static int MAX_NUM = 500000;
	bool *sieve;

	char getFromBuf()
	{
		if (st >= len)
		{
			len = fread(inBuf, sizeof(char), MAX_BUF, stdin);
			st = 0;
		}
		return inBuf[st++];
	}
	int intFromBuf()
	{
		char c = getFromBuf();
		while (c < '0' || '9' < c && len)
		{
			c = getFromBuf();
		}
		int num = 0;
		while ('0' <= c && c <= '9' && len)
		{
			num = (num<<3) + (num<<1) + (c - '0');
			c = getFromBuf();
		}
		return num;
	}

	void wrToBuf(int num, char sep)
	{
		if (oSt > FLASH_P)
		{
			fwrite(outBuf, sizeof(char), oSt, stdout);
			oSt = 0;
		}
		if (0 == num)
		{
			outBuf[oSt++] = '0';
			outBuf[oSt++] = sep;//漏了这句错误
			return;
		}
		char chs[12];
		int i = 0;
		while (num)
		{
			chs[i++] = num % 10 + '0';//这里居然忘记步进i错误
			num /= 10;
		}
		for (i--; i >= 0; i--)
		{
			outBuf[oSt++] = chs[i];
		}
		outBuf[oSt++] = sep;
	}
	inline void flashLeft()
	{
		if (oSt) fwrite(outBuf, sizeof(char), oSt, stdout);
	}
public:
	DivisorSummation47() : st(0), len(0), oSt(0)
	{
		int sq = (int)sqrt(double(MAX_NUM));
		sieve = (bool *) calloc(sizeof(bool), sq+1);
		//fill(sieve, sieve+sq+1, false);
		vector
  
    primes;
		for (int i = 2; i <= sq; i++)
		{
			if (!sieve[i])
			{
				for (int j = (i<<1); j <= sq; j += i)
				{
					sieve[j] = true;
				}
				primes.push_back(i);
			}
		}

		int T = 0;
		T = intFromBuf();
		while (T--)
		{
			int num = intFromBuf();
			int N = num;
			vector
   
     divs(1, 1); for (int i = 0; i < (int)primes.size() && num > 1; i++) { int d = primes[i]; if (d*d > num) d = num; if (num % d == 0) { int deg = 0; for ( ; num % d == 0; num /= d) deg++; for (int j = (int)divs.size() - 1; j >= 0 ; j--) { int t = divs[j]; for (int k = 0; k < deg; k++) { t *= d; divs.push_back(t); } } } } int ans = -N; for (int i = 0; i < (int)divs.size(); i++) { ans += divs[i]; } wrToBuf(ans, '\n'); }//while(T--) flashLeft(); } };