首页 > 编程语言 >挑战程序设计竞赛 2.6章习题 poj 3421 X-factor Chains

挑战程序设计竞赛 2.6章习题 poj 3421 X-factor Chains

时间:2024-03-28 15:12:48浏览次数:26  
标签:Xi 3421 length 测试用例 poj factor 长度 习题 chains

https://vjudge.net/problem/POJ-3421#author=GPT_zh

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 ≤ 2^20).

Output
For each test case, output the maximum length and the number of such X-factors chains.

2
3
4
10
100

1 1
1 1
2 1
2 2
4 6
给定一个正整数 X,长度为 m 的 X 因子链是一个整数序列,1 = X0, X1, X2, …, Xm = X
满足Xi < Xi+1 且 Xi | Xi+1,其中 a | b 表示 a 完全整除 b。
现在我们对 X 因子链的最大长度和该长度的链的数量感兴趣。

输入
输入包含多个测试用例。每个测试用例包含一个正整数 X (X ≤ 2^20)。

输出
对于每个测试用例,输出最大长度和该长度的 X 因子链的数量。

2
3
4
10
100

1 1
1 1
2 1
2 2
4 6

解答:
一道好题目 可以用多种方案解决

  1. 分解约数 dp得到最长路径和最长路径数目
  2. 分解质因数 dfs获得最长路径的数目
  3. 分解质因数 使用排列组合直接得到最长路径数目

标签:Xi,3421,length,测试用例,poj,factor,长度,习题,chains
From: https://www.cnblogs.com/itdef/p/18101725

相关文章

  • C语言经典练习题
    题目       学习成绩>=90分的同学用A表示,60-89分之间的用B表示,60分以下的用C表示。编程解析: 思路1:条件运算符:运用实例a>b?a:b 思路2:ifelse结构的运用 思路3:switchcase结构的运用//思路1:#include<stdio.h>intmain(intargc,charconst*argv[]){i......
  • 学点儿数据库_Day12_数据库SQL练习题
    0版本与工具mysql-8.0.31NavicatPremium16每做一题,选中相应代码运行即可,很方便1建表createtablegoods(goods_idmediumint(8)unsignedprimarykeyauto_increment,goods_namevarchar(120)notnulldefault'',cat_idsmallint(5)unsignednotnu......
  • 选择排序的练习题及答案(共三种方式实现选择排序)
    习题1班级里五个人成绩比较升序排列,成绩分别为64,75,88,92,21packagexuanze;importjava.util.*;publicclasschapter1{ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub Scannerscan=newScanner(System.in); intn=scan.nextInt......
  • 冒泡排序的习题全集(含答案)
    习题11.给定一个包含红色,白色和蓝色,共n个元素的数组nums,原地对他们进行排序,使得相同颜色的元素相邻,并按照共色,白色,蓝色顺序排列。我们使用整数0,1,2分别表示红色,白色,蓝色packagemaopao;importjava.util.*;publicclasschapter1{ publicstaticvoidmain(String[]ar......
  • 30道Python基础练习题
    大家好,我是程序媛学姐,今天为大家梳理了30道Python基础练习题,方便大家学习参考。1.编写一个程序,输出"Hello,World!"这个程序的目标是简单地输出一条消息,即"Hello,World!"。在Python中,可以使用print语句来实现这个功能。示例代码:#输出"Hello,World!"print("Hello,......
  • 蓝桥杯练习题总结(三)线性dp题(摆花、数字三角形加强版)
    目录 一、摆花思路一: 确定状态:初始化:思路二:确定状态:初始化:循环遍历: 状态转移方程: 二、数字三角形加强版一、摆花题目描述小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共m盆。通过调查顾客的喜好,小明列出了顾客最喜欢的n种花,从1到n标号。为了......
  • 蓝桥杯练习题——博弈论
    1.必胜态后继至少存在一个必败态2.必败态后继均为必胜态Nim游戏思路23,先手必赢,先拿1,然后变成22,不管后手怎么拿,先手同样操作,后手一定先遇到00a1^a2^a3…^an=0,先手必败,否则先手必胜#include<iostream>usingnamespacestd;constintN=1e5+1......
  • 第九章总练习题
    赫尔曼·阿曼杜斯·施瓦茨大学初期攻读化学,在魏尔斯特拉斯等人的建议下改攻读数学。施瓦茨在哈雷、哥廷根和柏林工作,范围涉及函数论、微分几何和变分学。以他为名的有柯西-施瓦茨不等式、施瓦茨导数、施瓦茨-克里斯托费尔映射、施瓦茨反射原理和施瓦茨引理。 施瓦茨,即德国数学......
  • 软件工程与实践(第四版 新形态)第3章习题答案详解
    第三章一、填空题二、选择题三、简答题四、实践题一、填空题(1)方法或服务(2)类对象(3)类对象继承消息通信二、选择题(1)B(2)C(3)C(4)B(5)D三、简答题(1)什么叫面向对象?面向对象方法OOM的特点是什么?为什么用OOM开发软件?面向对象是一种软件开发方法,它将数据和操作数据的......
  • Scala函数练习题
    1、定义一个高阶函数,按照指定的规则对集合里面的每个元素进行操作比如:Array(“hh”,“red”,“java”,“hadoop”)规则:对集合中每个元素进行操作,得到集合每个元素的长度objecttest{defmain(args:Array[String]):Unit={vallist=Array("hh","red","ja......