纪中18日c组模拟赛具体是哪一天举行的？

本文共计1430个文字，预计阅读时间需要6分钟。

题目：T4+GMOJ1574.+X-因子链（File IO）：输入：factor.in输出：factor.out时间限制：1000 ms空间限制：131072 KB总体限制：Goto ProblemSet题目描述：给定一个正整数X，一个长度为m的X-因子链是指这样一个序列：X0=1，X1=X，Xi=Xi-1*Pi（其中Pi是Xi-1的因子），序列长度为m。请输出X-因子链的长度。

T4 GMOJ1574. X-因子链

(File IO):input:factor.inoutput:factor.out

时间限制:1000 ms空间限制:131072 KB具体限制

Goto ProblemSet

题目描述

　　给一个正整数X，一个长度为m的X-因子链是指这样一个序列：X0=1，X1，X2，。。。，Xm=X满足：Xi<Xi+1同时Xi|Xi+1(Xi+1能被Xi整除)

　　要求X-因子链的最大长度Len和长度为Len的X-因子链的数量。

输出

　　一行，两个整数，分别表示最大长度和该长度链的种数。

样例输入

　　100

样例输出

　　4 6

数据范围限制

（空）

Solution

稍作思考即可

P1问题转化

有一个数列，已知首项（为1）与尾项，每一项都是前一项的整数倍，且每一项都大于前一项。

如何使此数列最长？

设相邻两项的商为k

那么k一定是越小越好

但是所有k之积必须等于尾项

那么，k即为尾项的所有质因数。

所以第一问只需求x的质因数个数。

P1Code

int maxlen=0x3f3f3f3f,kind,x; int lian[10000000]; IL int prime_factor(int num) { int ans=0; if(num==1) return 1; if(num==2) return 1; int i=2; while(num!=1) { while(num%i==0) { num/=i; ans++; lian[i]++; } i++; } return ans; }

（使用IL（inline）加速调用）

填写lian[i]++是为了第二问的

P2看穿此题

排列组合类型题

因子链的数量，即这些prime factors可以排成多少种

以样例中的100为例

100=2*2*5*5=2²*5²

那么这串链有两种、四个元素

不去重的话，一共有4!种排列

但是这道题是要问的是种类（即去重的）数量……

现在只观察其中的两个2

2*2*？*？

这时两个2如果交换，会被算入全排列的数量中，但是不能被算入种类数量中！

两个2可以有两种摆放位置的顺序

那么4!=24除去两次2（两个2和两个5的）即可。

若有三个2呢？

三个2可以有3!=3*2*1=6种摆放位置的顺序

把n!除以6即可。

P2数学推导

设

其中ans为质因数的数量

所以

P2Code

若数据较小（不存在的），可使用dfs暴力枚举

1 IL void dfs(int depth) 2 { 3 if(depth==maxlen){ 4 kind++; 5 return; 6 } 7 for(int i=1;i<=x;i++) 8 { 9 if(lian[i]>0){ 10 lian[i]--; 11 dfs(depth+1); 12 lian[i]++; 13 } 14 } 15 } dfs暴力枚举

于是20分……枉费了我辛辛苦苦思考呀！

阶乘运算

1 IL long long factor(int num) 2 { 3 if(num==0) return 1; 4 long long ans=1; 5 for(int i=1;i<=num;i++) 6 ans*=i; 7 return ans; 8 } factor

如果只是按照普通的阶乘的话，比较容易爆long long

解决方案有两种：

1、预处理（或者打表、记忆化……）出1~20的阶乘（极限应该是31！，但会超过unsigned long long，且数据也没有那么大哈哈），factor函数可用递归。

1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<map> 6 #include<set> 7 #include<vector> 8 #include<algorithm> 9 #define IL inline 10 using namespace std; 11 int lian[50000]; 12 unsigned long long kind,maxlen=0x3f3f,x; 13 unsigned long long fact[32]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000}; 14 IL unsigned long long factor(int num) 15 { 16 if(fact[num]!=0) return fact[num]; 17 return fact[num]=factor(num-1)*num; 18 } 递归加打表

如果记忆化的话，其实就可以不用打表了（反正都是2、3毫秒的样子）。

2、把一个数的阶乘分解成

这样子

用结构体数组储存。

最后要相除则换成相减即可

——来自某某不让我去B组的老师的想法

Code

1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<map> 6 #include<set> 7 #include<vector> 8 #include<algorithm> 9 #define IL inline 10 using namespace std; 11 int lian[50000]; 12 unsigned long long kind,maxlen=0x3f3f,x; 13 unsigned long long fact[32]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000}; 14 IL int prime_factor(int num) 15 { 16 int ans=0; 17 if(num==1) return 1; 18 if(num==2) return 1; 19 int i=2; 20 while(num!=1) 21 { 22 while(num%i==0) 23 { 24 num/=i; 25 ans++; 26 lian[i]++; 27 } 28 i++; 29 } 30 return ans; 31 } 32 IL unsigned long long factor(int num) 33 { 34 if(fact[num]!=0) return fact[num]; 35 return fact[num]=factor(num-1)*num; 36 } 37 int main() 38 { 39 // freopen("factor.in","r",stdin); 40 // freopen("factor.out","w",stdout); 41 scanf("%lld",&x); 42 maxlen=prime_factor(x); 43 printf("%lld ",maxlen); 44 kind=factor(maxlen); 45 for(unsigned long long i=1;i<=sqrt(x);i++) 46 if(lian[i]>1) 47 kind/=factor(lian[i]); 48 printf("%lld",kind); 49 return 0; 50 }

这道题的代码在尝试着极限……0ms，512KB！

可是……真的有0ms……