POJ 3421
2024-10-12 05:40:45
X-factor Chains
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 5111 | Accepted: 1622 |
Description
Given a positive integer X, an X-factor chain of length m is a sequence of integers,
1 = X0, X1, X2, …, Xm = X
satisfying
Xi < Xi+1 and Xi | Xi+1 where a | b means a perfectly divides into b.
Now we are interested in the maximum length of X-factor chains and the number of chains of such length.
Input
The input consists of several test cases. Each contains a positive integer X (X ≤ 220).
Output
For each test case, output the maximum length and the number of such X-factors chains.
Sample Input
2
3
4
10
100
Sample Output
1 1
1 1
2 1
2 2
4 6
Source
POJ Monthly--2007.10.06, ailyanlu@zsu
找出x的所有质因子表达式,最大长度就是各质因子指数的和,然后按照排列组合计算即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std; #define maxn (1 << 20) + 5 typedef long long ll; int x,len = ;
bool prime[maxn];
int ele[]; ll cal(int x) {
ll ans = ;
for(int i = ; i <= x; i++) ans *= i; return ans;
} void init() {
for(int i = ; i <= maxn - ; i++) {
prime[i] = i % || i == ;
} for(int i = ; i * i <= maxn - ; i++) {
if(!prime[i]) continue;
for(int j = i; j * i <= maxn - ; j++) {
prime[j * i] = ;
}
} len = ;
for(int i = ; i <= maxn - ; i++) {
if(prime[i])
ele[len++] = i;
} }
int main() {
//freopen("sw.in","r",stdin); init(); while(~scanf("%d",&x)) {
if(prime[x]) {
printf("1 1\n");
} else {
int ans1 = ,len2 = ;
ll ans2 = ;
int num[];
for(int i = ; i < len && ele[i] <= x && x != ; i++) {
int sum = ;
if(x % ele[i] == ) {
while(x % ele[i] == ) {
ans1++;
sum++;
x /= ele[i];
}
num[len2++] = sum;
} } ans2 = cal(ans1);
for(int i = ; i < len2; i++) {
ans2 /= cal(num[i]);
}
printf("%d %I64d\n",ans1,ans2); } } return ;
}
最新文章
- SpingMvc中的异常处理
- 关于Leetcode上二叉树的算法总结
- Es6 学习笔记
- LoadRunner11.00入门教程出现的问题
- 由ArrayList构造函数源码引出的问题
- JSP页面跳转方式
- Kali vmtools
- Swift数组的加法运算符用法:array1 += array2
- 自学JavaScript笔记
- 【@Transactional】Spring 之注解事务 @Transactional
- 关于textView的字数限制
- 给postgresql 创建新的用户
- MySQL2.字符集乱码
- 墨者学院——密码学加解密实训(Base64转义)
- 剑指Offer 38. 二叉树的深度 (二叉树)
- 【浅说】堆(heap)和栈(stack)区别
- ubuntu远程桌面、VNC(转载)
- python3+pyqt5 +eric5安装配置
- CDN、浏览器缓存
- PyCharm引入自定义类报错