Language:
X-factor Chains
Time Limit:1000MSMemory Limit:65536K
Total Submissions:5603Accepted:1768
Description
Given a positive integerX, anX-factor chain of lengthmis a sequence of integers,
1 =X0,X1,X2, …,Xm=X
satisfying
Xi<Xi+1andXi|Xi+1wherea|bmeansaperfectly divides intob.
Now we are interested in the maximum length ofX-factor chains and the number of chains of such length.
Input
The input consists of several test cases. Each contains a positive integerX(X≤ 220).
Output
For each test case, output the maximum length and the number of suchX-factors chains.
Sample Input
23410100
Sample Output
1 11 12 12 24 6
Source
, ailyanlu@zsu
题意：给出一个数X，现在定义1 = X0, X1, X2, …, Xm = X，，其中Xi能被Xi-1整除，问满足该定义的最大m和满足最大的个数有多少。思路：质因子们的排列组合——∏(质因子个数的阶乘)/(每个质因子的个数的阶乘)。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 1005#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;//vector<int>//只求解整数分解的因子的幂vector<int> prime_factor_time(int n){vector<int> res;for (int i=2;i*i<=n;i++){int time=0;while (n%i==0){++time;n/=i;}res.push_back(time);}if (n!=1)res.push_back(1);return res;}//阶乘ll factor(const int& n){ll res=1;for (int i=1;i<=n;i++)res*=i;return res;}int main(){int i,j,x;while (~sf(x)){vector<int> num=prime_factor_time(x);int all=0;vector<int>::iterator it;for (it=num.begin();it!=num.end();it++)all+=*it;ll ans=factor(all);for (it=num.begin();it!=num.end();it++)ans/=factor(*it);pf("%d %lld\n",all,ans);}return 0;}
如果有可能，我带你去远行。
