2002
题二最大公约数与最小公倍数问题（20分）
[问题描述]
输入二个正整数x0,y0（2≤x0<100000,2≤y0≤1000000）,求出满足下列条件的P，Q的个数：
条件：1. P,Q是正整数
2. 要求P,Q以x0为最大公约数，以y0为最小公倍数。

试求：满足条件的所有可能的两个正整数的个数。

[样例]
输入：x0=3 y0=60
输出：4
说明：（不用输出）此时的 P Q 分别为：
3 60
15 12
12 15
60 3
所以：满足条件的所有可能的两个正整数的个数共4种。

2012
1.质因数分解
(prime.cpp/c/pas)
【问题描述】
已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。

【输入】
输入文件名为prime.in。

输入只有一行，包含一个正整数n。

【输出】
输出文件名为prime.out。

输出只有一行，包含一个正整数p，即较大的那个质数。

【输入输出样例】
prime.in prime.out
21 7
【数据范围】
对于60%的数据，6 ≤ n ≤ 1000。

对于100%的数据，6 ≤ n ≤ 2*109。

2007年
4.Hanoi双塔问题
hanoi.pas/c/cpp
【问题描述】
给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。

现要将这些国盘移到C柱上，在移动过程中可放在B柱上暂存。

要求:
(1)每次只能移动一个圆盘；
(2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。

【输入】
输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。

【输出】
输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。

【限制】
对于50%的数据， 1<=n<=25
对于100% 数据， 1<=n<=200
【提示】
设法建立An与An-1的递推关系式。

2006年
4.数列
（sequence.pas/c/cpp）
【问题描述】
给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：
1，3，4，9，10，12，13，…
（该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，…）
请你求出这个序列的第N项的值（用10进制数表示）。

例如，对于k=3，N=100，正确答案应该是981。

【输入文件】
输入文件sequence.in 只有1行，为2个正整数，用一个空格隔开：
k N
（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。

【输出文件】
输出文件sequence.out 为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*109）。

（整数前不要有空格和其他符号）。

【输入样例】
3 100
【输出样例】
981
2005年noip普及组
循环
(circle.pas/c/cpp)
【问题描述】
乐乐是一个聪明而又勤奋好学的孩子。

他总喜欢探求事物的规律。

一天，他突然对数的正整数次幂产生了兴趣。

众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6……我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。

类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：
循环
循环长度
2
2、4、8、6
4
3
3、9、7、1
4
4
4、6
2
5
5
1
6
6
1
7
7、9、3、1
4
8
8、4、2、6
4
9
9、1
2
这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数n的正
整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？
注意：
1．如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。

2．如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a + L次幂的最后k 位都相同。

【输入文件】
输入文件circle.in只有一行，包含两个整数n（1 <= n < 10100）和k（1 <= k <= 100），n和k之间用一个空格隔开，表示要求n的正整数次幂的最后k位的循环长度。

【输出文件】
输出文件circle.out包括一行，这一行只包含一个整数，表示循环长度。

如果循环不存在，输出-1。

【样例输入】
32 2
【样例输出】
4
【数据规模】
对于30%的数据，k <= 4；
对于全部的数据，k <= 100。

2009年noip普及组复赛
3．细胞分裂
(cell.pas/c/cpp)
【问题描述】
Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家。

现在，他正在为一个细胞实
验做准备工作：培养细胞样本。

Hanks 博士手里现在有N 种细胞，编号从1~N，一个第i 种细胞经过1 秒钟可以分裂为Si 个同种细胞（Si 为正整数）。

现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，进行培养。

一段时间以后，再把培养皿中的所有细胞平均分入M 个试管，形成M 份样本，用于实验。

Hanks 博士的试管数M 很大，普通的计算机的基本数据类型无法存储这样大的M 值，但万幸的是，M 总可以表示为m1 的m2 次方，即2
1
M = m m ，其中m1，m2 均为基本
数据类型可以存储的正整数。

注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有4 个细胞，Hanks 博士可以把它们分入2 个试管，每试管内2 个，然后开始实验。

但如果培养皿中有5
个细胞，博士就无法将它们均分入 2 个试管。

此时，博士就只能等待一段时间，让细胞们继
续分裂，使得其个数可以均分，或是干脆改换另一种细胞培养。

为了能让实验尽早开始，Hanks 博士在选定一种细胞开始培养后，总是在得到的细胞“刚好可以平均分入M 个试管”时停止细胞培养并开始实验。

现在博士希望知道，选择哪种细胞培养，可以使得实验的开始时间最早。

【输入】
输入文件名为cell.in，共有三行。

第一行有一个正整数N，代表细胞种数。

第二行有两个正整数m1，m2，以一个空格隔开，2
1
m m 即表示试管的总数M。

第三行有N 个正整数，第i 个数Si 表示第i 种细胞经过1 秒钟可以分裂成同种细胞的个数。

【输出】
输出文件cell.out 共一行，为一个整数，表示从开始培养细胞到实验能够开始所经过的
最少时间（单位为秒）。

如果无论Hanks 博士选择哪种细胞都不能满足要求，则输出整数-1。

【输入输出样例1】
cell.in cell.out
1
2 1
3
-1
【输入输出样例1 说明】
经过1 秒钟，细胞分裂成3 个，经过2 秒钟，细胞分裂成9 个，……，可以看出无论怎么分
裂，细胞的个数都是奇数，因此永远不能分入2 个试管。

2009-11-21 18:58 回复
59.33.120.* 5楼
【输入输出样例2】
cell.in cell.out
2
24 1
30 12
2
【输入输出样例2 说明】
第1 种细胞最早在3 秒后才能均分入24 个试管，而第2 种最早在2 秒后就可以均分（每试管144/(241)=6 个）。

故实验最早可以在2 秒后开始。

【数据范围】
对于50%的数据，有2
1
m m ≤30000。

对于所有的数据，有1 ≤N≤10000，1 ≤m1 ≤30000，1 ≤m2 ≤10000，1 ≤Si ≤2,000,000,000。