Uva 11960: Divisor Game

解題心得

原本的想法是用質數篩法建質數表，然後一個個用質因數分解找因數，因為一個數的因數數量就是質因數次方加一的乘積。

例：36 = 2^2 + 3^2，其因數數量為(2+1)*(2+1)=9。背後原因很簡單就不贅述。

不過寫完後發現會TLE，只好放棄。

參考了CPE提供的參考解法，發現解法其實很簡單。首先同樣要建表，這次建的是因數表。何謂因數？就是某數可以整除的數。反過來想，把某數的倍數與自己通通都加一，因為一定能整除。

為了近一步縮短時間，提前建好答案表。答案表紀錄從1~i的範圍內，因數數量最多的是誰。注意若數量相同，也要更新。

講起來很容易，但就是想不到啊。

程式碼

#include <iostream>
using namespace std;

#define SIZE 1000001

int table[SIZE] = { 0 }, ans[SIZE] = { 0 };

int main()
{
	for (int i = 1; i < SIZE; i++)
	{
		for (int j = i; j < SIZE; j += i)
			table[j]++;
	}
	int maxIndex = 1, maxCount = 0;
	for (int i = 1; i < SIZE; i++)
	{
		if (table[i] >= maxCount)
		{
			maxIndex = i;
			maxCount = table[i];
		}
		ans[i] = maxIndex;
	}
	
	int T, n;
	cin >> T;
	while (T--)
	{
		cin >> n;
		cout << ans[n] << endl;
	}
	return 0;
}