POJ 3421 X-factor Chains 埃氏筛法+质因子分解+DFS

一、思路

我们先用埃氏筛法，找出1048576范围内的素数，其实找出1024以内的就够了，但是1048576也不大，所以无所谓了。

然后把输入的数字不断的判断与每个素数是否整除，然后把输入的数变为很多个素数相乘的形式，最后素数的个数就是这个X-fcactor chains的长度。

然后种类数的话，需要把这些素数写成次方的形式，比如200=(2^3)*(5^2)，然后针对2，5，dfs，判断每个数乘上去与不乘上去的情况，一直到每个数都乘上去的情况是递归出口，然后结果+1.

例如100=(2^2)*(5^2)

2^0*5^0->2^1*5^0->2^2*5^0->2^2*5^1->2*2*5^2

2^0*5^0->2^1*5^0->2^1*5^1->2^2*5^1->2*2*5^2

2^0*5^0->2^1*5^0->2^1*5^1->2^1*5^2->2*2*5^2

2^0*5^0->5^1*2^0->2^1*5^1->2^2*5^1->2*2*5^2

2^0*5^0->5^1*2^0->2^1*5^1->2^1*5^2->2*2*5^2

2^0*5^0->5^1*2^0->2^0*5^2->2^1*5^2->2*2*5^2

这样也就得出6种，（算式中，我用2^5代表2的5次方，2*2*5^2代表2的平方乘以5的平方。

二、代码

#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
bool isPrime[1049007];
int n = 1049007, p;
vector<int> primeVector;
vector<int> facArray;
vector<int> distinctArray;
vector<int> countArray;
ll ansCount = 0;
int dfsArray[100];
void sieve()
{for (int i = 0; i <= 1049000; i++){isPrime[i] = true;}isPrime[0] = false, isPrime[1] = false;for (int i = 1; i * i <= 1049000; i++){if (!isPrime[i]){continue;}for (int j = i * 2; j <= 1049000; j += i){isPrime[j] = false;}}
}
void initPrimeVector()
{for (int i = 0; i <= 1049000; i++){if (isPrime[i]){primeVector.push_back(i);}}
}
void getFacArray()
{for (int i = 0; i < primeVector.size(); i++){if (isPrime[p]){facArray.push_back(p);break;}else if (p <= 1){break;}int primeNumber = primeVector[i];while (p % primeNumber == 0){facArray.push_back(primeNumber);p = p / primeNumber;}}
}
void flushVector()
{if (distinctArray.size() > 0){distinctArray.clear();}if (countArray.size() > 0){countArray.clear();}if (facArray.size() > 0){facArray.clear();}
}
void calc()
{map<int, int> countMap;set<int> distinctSet;for (int i = 0; i < facArray.size(); i++){countMap[facArray[i]] = 0;distinctSet.insert(facArray[i]);}for (int i = 0; i < facArray.size(); i++){int count = countMap[facArray[i]];countMap[facArray[i]] = count + 1;}for (set<int>::iterator ite = distinctSet.begin(); ite != distinctSet.end(); ite++){int number = *ite;distinctArray.push_back(number);}sort(distinctArray.begin(), distinctArray.end());for (int i = 0; i < distinctArray.size(); i++){countArray.push_back(countMap[distinctArray[i]]);}
}
void dfs(int sum)
{if (sum == facArray.size()){ansCount++;return;}for (int i = 0; i < distinctArray.size(); i++){if (dfsArray[i] < countArray[i]){dfsArray[i]++;dfs(sum + 1);dfsArray[i]--;}}
}
int main()
{sieve();initPrimeVector();while (~scanf("%d", &p)){ansCount = 0;getFacArray();calc();vector<int> array;for (int i = 0; i < distinctArray.size(); i++){dfsArray[i] = 0;}dfs(0);printf("%d %lld\n", facArray.size(), ansCount);flushVector();}return 0;
}