网站怎么做交易,深圳微信公众号,怎样做聊天网站,徐州英文网站seo一、思路
我们先用埃氏筛法#xff0c;找出1048576范围内的素数#xff0c;其实找出1024以内的就够了#xff0c;但是1048576也不大#xff0c;所以无所谓了。
然后把输入的数字不断的判断与每个素数是否整除#xff0c;然后把输入的数变为很多个素数相乘的形式#xf…一、思路
我们先用埃氏筛法找出1048576范围内的素数其实找出1024以内的就够了但是1048576也不大所以无所谓了。
然后把输入的数字不断的判断与每个素数是否整除然后把输入的数变为很多个素数相乘的形式最后素数的个数就是这个X-fcactor chains的长度。
然后种类数的话需要把这些素数写成次方的形式比如200(2^3)*(5^2)然后针对25dfs判断每个数乘上去与不乘上去的情况一直到每个数都乘上去的情况是递归出口然后结果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;
vectorint primeVector;
vectorint facArray;
vectorint distinctArray;
vectorint 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()
{mapint, int countMap;setint 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 (setint::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();vectorint array;for (int i 0; i distinctArray.size(); i){dfsArray[i] 0;}dfs(0);printf(%d %lld\n, facArray.size(), ansCount);flushVector();}return 0;
}
