一本通1628X-factor Chain
2024-09-09 03:33:36
1628:X-factor Chain
时间限制: 1000 ms 内存限制: 524288 KB
【题目描述】
原题来自 POJ 3421
输入正整数 x,求 x 的大于 1 的因子组成的满足任意前一项都能整除后一项的序列的最大长度,以及满足最大长度的序列的个数。
【输入】
多组数据,每组数据一行,包含一个正整数 x。
【输出】
对于每组数据,输出序列的最大长度以及满足最大长度的序列的个数。
【输入样例】
2
3
4
10
100
【输出样例】
1 1
1 1
2 1
2 2
4 6
【提示】
数据范围与提示:
对于全部数据,1≤x≤220。
sol:看上去难系列
稍微想一下,发现是个排列组合一样的东西,又因为因数最多20,20!都没爆long long,随便搞搞
对于第 i 个质因数 有G[i] 个,一共有cnt个质因数
cnt
序列的最大长度Len就是 ∑ G[i]
i=1
cnt
方案数就是Len! / ∏ G[i]!
i=1
代码实现复杂度接近于0。。。。
Ps:吐槽这里的sigma好难用啊qaq
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll s=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=;
ll n;
ll Ges[N];
int main()
{
while(~scanf("%lld",&n))
{
ll i,nn=n,ans1=,ans2=;
*Ges=;
for(i=;i<=sqrt(nn);i++) if(nn%i==)
{
ll tmp=;
Ges[++*Ges]=;
while(nn%i==)
{
nn/=i;
tmp*=(++Ges[*Ges]);
ans2*=(++ans1);
}
ans2/=tmp;
}
if(nn>)
{
Ges[++*Ges]=; ans1++; ans2*=ans1;
}
W(ans1); Wl(ans2);
}
return ;
}
最新文章
- hadoop入门(1)——hadoop概述
- UIKit框架之UIGestureRecognizer
- SHELL实现同时操作多个服务器:服务器批量管理
- Gym 100851K
- [转]MySQL数据库引擎
- 转——Android测试之monkey
- cdoj 1329 卿学姐与魔法 优先队列
- Python十分钟入门
- 简单的猜数字(JAVA版)
- C#中常量\枚举\结构及数组的运用
- 微信JS-SDK“分享信息设置”API及数字签名生成方法(NodeJS版本)
- javascript对象转换,动态属性取值
- Unable to add window -- token android.os.BinderProxy@3a067204 is not valid错误分析记录
- ubuntu14.04 64位 安装JDK1.7
- Chinese-Text-Classification,用卷积神经网络基于 Tensorflow 实现的中文文本分类。
- JS 设计模式七 -- 模板方法模式
- docker swarm 搭建与服务更新
- css 两段对齐和超出部分...
- csrfguard3.1 部署笔记
- February 7th, 2018 Week 6th Wednesday