类似于动态规划, 定义len[x]和num[x]两个数组, 分别表示1到x的最长路径长和最长路径数目. 枚举1到X中的每个整数(不只是素数)i, 对于i枚举i在X以内的所有倍数j, 在这个时候len[i]和num[i]都是已知的, 因此我们用这两个信息计算i对j的贡献, 如果len[i] + 1 > len[j], 则说明之前计算得到的到j的路径长应该被舍弃, 应当对len[j]进行更新, 并且将num[j]直接改为num[i], 如果len[i] + 1 == len[j], 说明发现了新的长度一样的路径, 那么把num[i]加到num[j]上. 完成预处理后对每个询问O(1)查询. 至于为什么预处理的复杂度是O(X log X), 因为预处理过程中循环的次数等于 X/1 + X/2 +X/3 ... +X/X, 提取各项的公因子X后剩下的是一个调和级数, 渐进上=O(log X), 因此总的复杂度是O(X log X).

code:

/*solution to POJ-3421:X-factor Chains*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_X (1<<20)

int len[MAX_X + 1];
int num[MAX_X + 1];
vector<int> arr;

int main(void)
{
	int x;
	int mxx = 0;
	while(cin >> x){
		arr.push_back(x);
		mxx = max(mxx, x);
	}
	
	len[1] = 0;
	num[1] = 1;
	for(int i = 1; i <= mxx; i++){
		for(int j = 2*i; j <= mxx; j += i){
			if(len[i] + 1 > len[j]){
				len[j] = len[i] + 1;
				num[j] = num[i];
			}else if(len[i] + 1 == len[j]){ 
				num[j] += num[i];
			}
		}
	}
	for(int i = 0; i < arr.size(); i++)
		cout << len[arr[i]] << ' ' << num[arr[i]] << '\n';
	return 0;
}