POJ 3421 X-factor Chains | 数论
2024-09-28 23:11:11
题意:
给一个x,求最长的排列满足开头是1,结尾是x,前一个数是后一个数的因子
输出长度和这样序列的个数
题解:
把x分解质因数,质因数个数就是答案,接下来考虑怎么求个数
显然这是一个可重集合全排列问题,设有n个元素
答案就是n!/每个元素出现次数的阶乘
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
#define N 2000
using namespace std;
int prime[N],n,cnt[N],pcnt,sum;
ll jc[];
bool isp[N];
void init()
{
memset(isp,,sizeof(isp));
isp[]=;
for (int i=;i<N;i++)
{
if (isp[i]==)
prime[++pcnt]=i;
for (int j=;j<=pcnt && i*prime[j]<N;j++)
{
isp[i*prime[j]]=;
if (i%prime[j]==) break;
}
}
}
int main()
{
jc[]=;
for (int i=;i<=;i++)
jc[i]=jc[i-]*i;
init();
while (scanf("%d",&n)!=EOF)
{
ll ans=;
memset(cnt,,sizeof(cnt));
sum=;
for (int i=;i<=pcnt;i++)
{
if (n==) break;
while (n%prime[i]==)
n/=prime[i],cnt[i]++,sum++;
}
if (n>)
sum++;
ans=jc[sum];
for (int i=;i<=pcnt;i++)
ans/=jc[cnt[i]];
printf("%d %lld\n",sum,ans);
}
return ;
}
最新文章
- Android网络编程1
- ";\r\n";,";\r";,";\n";
- 【BZOJ 2157】旅游
- weblogic sockets 和 thread 问题解决
- 重学STM32---(六)DAC+DMA+TIM
- .NET程序与CA对接一直提示重定向
- SQL中and与or优先级比较
- Context
- Oracle SQL Lesson (9) - 操作数据(增删改)
- What skills are needed for machine learning jobs
- CDockablePane 关闭的问题
- mysql授权远程用户连接(权限最小化原则)
- 初学Python之 字符串 索引 分片
- XAMARIN 安卓程序闪退问题
- javaScript判断手机型号
- paiza
- Docker 部署Django项目
- 【POI每日题解 #5】 DWU-Double-row
- Telnet Protocol Specification
- hibernate 多对一(级联)操作