X-factor Chain（信息学奥赛一本通 1628）

题目描述

输入正整数 x，求 x 的大于 1 的因子组成的满足任意前一项都能整除后一项的序列的最大长度，以及满足最大长度的序列的个数。

输入

多组数据，每组数据一行，包含一个正整数 x。

对于全部数据，1≤x≤220。

输出

对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。

样例输入

2

3

4

10

100 样例输出

1 1

2 1

2 2

4 6

这道题虽然是“约数”的练习，但其实我一开始一点关于约数的思路都没，后来去网上看别人的题解，然鹅基本上都是肥肠简单的一笔带过（类似“不难得到”“易得”之类的话），直接得出“序列的最大长度即x的质因子的总个数，而满足最大长度的序列的个数即x的所有质因子的全排列数”的结论，对于我这样的蒟蒻来说太不友善惹，我都看得一脸懵逼o((⊙﹏⊙))o

后来终于找到了这位大佬的题解↓↓↓，写的真是思路清晰，让我一下子恍然大悟。

点击进入大佬的博客

简要分析下这道题的题意：要使这个序列中的前一项都能整除后一项，即前一项必须是后一项的因子。我们设前一项为a，后一项为an，那么要使这个序列尽可能的长，就要让n尽可能的小，小到不能再进行分解，（假如n可以分解，即n=pq，且p、q都不等于1，那一定可以让这个序列变成更长的a,ap,ap*q，那么就不符题意了），那显然n不就是质数嘛，而a可以乘的n的个数就是我们要求的序列的最大长度。所以我们就可以将给定的x分解质因数，统计x一共有多少个质因子（我这里记为ans）。

其实完全可以将这个最长序列的每一项都看成是它的前一项所乘的质数（第一项的前一项可看作是1），那么这样，满足最大长度的序列个数，就是这些质数的不同排列方式的个数，即组合数学当中的“不全相异元素的排列”。所以排列数公式为：ans!/(c1!+c2!......+ck!)

 #include<bits/stdc++.h>

 #define ll long long

 using namespace std;

 const ll N=;

 int c[];

 ll f[N];

 ll fac(ll x)

 {

     if(f[x])return f[x];//记忆化搜索

     f[x]=x*fac(x-);

     return f[x];

 }

 int main()

 {

     ll x;f[]=;

     while(~scanf("%lld",&x))

     {

         ll cnt=,ans=;//每次都要更新

         memset(c,,sizeof(c));

         ll n=x;

         for(ll i=;i*i<=x;i++)

         {

             if(n%i==)

             {

                 cnt++;//cnt存x可分解出的质因子的种数

                 while(n%i==)

                 {

                     n/=i;

                     c[cnt]++;//第几种质因子在x里出现的个数

                     ans++;//ans指x里一共有多少个质因子

                 }

             }

         }

         if(n>)//如果还有一个大于sqrt(n)的质数

         {

             c[++cnt]++;

             ans++;

         }

         printf("%lld ",ans);

         ll nn=fac(ans);//nn=ans!

         for(int i=;i<=cnt;i++)

             nn/=fac(c[i]);

         printf("%lld\n",nn);

     }

     return ;

 }

详情请展开代码

现在觉得其实很简单的鸭，没有一点技巧，真搞不懂我之前居然没理解，看来是脑子没转过弯来。果然写一遍题解还是有点用的

巴特西

X-factor Chain（信息学奥赛一本通 1628）

题目描述

输入正整数 x，求 x 的大于 1 的因子组成的满足任意前一项都能整除后一项的序列的最大长度，以及满足最大长度的序列的个数。

输入

多组数据，每组数据一行，包含一个正整数 x。

对于全部数据，1≤x≤220。

输出

对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。

样例输入

2

3

4

10

100

样例输出

1 1

1 1

2 1

2 2

4 6

后来终于找到了这位大佬的题解↓↓↓，写的真是思路清晰，让我一下子恍然大悟。

点击进入大佬的博客

现在觉得其实很简单的鸭，没有一点技巧，真搞不懂我之前居然没理解，看来是脑子没转过弯来。果然写一遍题解还是有点用的

最新文章

热门文章