纪中18日c组模拟赛

发布时间：2020-12-16 09:19:23 所属栏目：百科来源：网络整理

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

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 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,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……

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!