纪中18日c组模拟赛_C

概述 T4 GMOJ1574. X-因子链 (File IO): input:factor.in output:factor.out 时间限制: 1000 ms 空间限制: 131072 KB 具体限制 Goto ProblemSet 题目描述　　给一个正整数X，一个长度为m的X-因子链是指这样一个序列：X0=1，X1，X2，。。。，Xm=X满足：Xi

T4 GMOJ1574. X-因子链

(file IO): input:factor.in output: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 inline10 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 inline10 using namespace std;11 int lian[50000];12 unsigned long long kind,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 }