第1章 2007年广东省青少年信息学重点中学邀请赛（GDKOI）试题分析
1.1 谁是天才（难度：★★★☆☆）
1.1.1 试题
题目描述
这天张大牛遇到了大肥熊。
张大牛：“我是天才！”
大肥熊：“你为什么是天才？”
张大牛：“你随便告诉我一个数字，我立即可以算出它的所有约数的和，以及所有约数的倒数和！”
大肥熊：“换过来，我告诉你一个数的所有约数（包括1和该数本身）的和，以及约数的倒数之和，你是天才你应该立即能推出这个数是什么！”
张大牛被难倒了！
现在，这个难倒了天才的题目就交到你的手上了。
输入格式
输入文件包含多组输入数据。
每组数据有三个正整数A，B1和B2（1≤A, B1, B2≤109），其中A为C的约数和，而对于C的所有约数的倒数之和B，为避免精度误差，以分数B1/B2的形式给出。
输入文件以一行“0 0 0”结束。
输出格式
对于输入的每一组数据输出一行，该行的第一个整数N是所有满足条件的不同的C的个数。其后按照从小到大的顺序输出N个数，为所有满足条件的C。相邻两个整数之间用空格隔开，行末不要有空格。
输入样例
18 9 5
1 1 2
1 1 1
0 0 0
输出样例
1 10
0
1 1
1.1.2 题目分析和算法实现
这是一道相对简单的数学题。
设自然数A为自然数B的一个约数，则显然B/A也为B的约数。于是，对自然数N的所有约数（假设共有M个）a1, a2, a3,…, am，数N/a1, N/a2, N/a3,…, N/am也均为N的约数，且与a1, a2, a3,…, am存在一种一一对应的关系。
因此，有
a1+a2+a3+…+am= N/ a1 +N/a2 +N/a3 +…+N/am=（1/a1 +1/a2 +1/a3 +…+1/am）*N
从而有
N=（a1+a2+a3+…+am）/（1/a1 +1/a2 +1/a3+…+1/am）
题中给出A=（a1+a2+a3+…+am）, B1/B2=（1/a1 +1/a2 +1/a3+…+1/am），由上述分析可知，若N存在，则答案必定唯一且等于（A*B2）/B1。
显然，如果（A*B2）不能被B1整除，则N必定不存在。否则，先计算出一个C=（A*B2）/B1，再判断C的约数和是否等于A。若等于则输出C作为唯一的答案，否则输出无解。
求C的所有约数之和，最直接的方法就是枚举1到sqrt（C）之间的所有自然数，判断每一个数是否为C的约数。
除了这种方法外，不难想出另一种较快的方法是对C做素因子分解。
设C=D*qk，其中q是一个素数，而D是一个与q互素的自然数，再用F（X）来表示X的所有约数之和。由于
（i）C的每个约数
Cdi，存在唯一的D的约数Ddj使得
Cdi / Ddj = qr（0≤r≤k）
（ii）D的每个约数Ddj，数Ddj，Ddj*q，Ddj*q2，Ddj*q3，…，Ddj*qk 都是C的约数。故有
F（C）= F（D）*（1+ q+ q2+ q3+…+qk）= F（D）*（qk+1 – 1）/（q – 1）
虽然两种方法在最坏情况下复杂度相同，都是O（sqrt（n）），但在实际应用中，第二种方法会快得多。在采用100000组随机数据的实际测试中，用第一种方法编写的程序运行100多秒后才结束，而用第二种方法编写的程序则能在2秒的时间内输出所有正确解。
1.1.3 参考程序及程序分析
#include＜stdio.h＞
#define maxn 1000000000 //最大n值
#define maxm 100000 //sqrt(n)
int a,b,c,ans,t; //ans为由a,b,c得出的答案，t为生成质数的数量
int q[maxm]; //质数表
bool p[maxm]; //质数标记表
void prepare() //利用筛法生成质数
{
int i,j;
t=0;
for (i=2;i＜maxm;i++) //枚举maxm以内的所有数字
if (!p[i]) {
//假如未被标记，表明2…i-1的所有倍数不包含i，即i是质数
q[++t]=i; //将质数i保存到数组q
if (maxm/i＞=i) //对所有比maxm小的i的倍数做标记
for (j=i＊i;j＜maxm;j+=i) p[j]=1;
}
}
int sumit(int a) //求a的约数之和
{
long long sum=1,now;
int i=1;
while (q[i]＊q[i]＜=a) {
if (a%q[i]==0) { //a能整除q[i]
//求出a所能整除的q[i]的最大幂now
now=1;
while (a%q[i]==0) {
a/=q[i];
now＊=q[i];
}
now＊=q[i];
now=(now-1)/(q[i]-1);
//now=(q∧(k+1)-1)/(q-1)，参考题解第2种方法的结论
sum＊=now;
if (sum＞∶∶a) return -1; //已经大于全局变量a了，必定无解
}
i++;
}
if (a＞1) { //a＞1表示a为未分解完的最后一个质数
now=a+1; //now=(a＊a-1)/(a-1)，即q=a,k=1，参考题解第二种方法的结论
sum＊=now;
}
return sum;
}
int main()
{
freopen("genius.in","r",stdin); //输入文件
freopen("genius.out","w",stdout); //输出文件
long long temp;
prepare();
while(scanf("%d %d %d",&a,&b,&c),a) { //输入a,b,c
temp=a;
if (temp＊c%b) printf("0\n"); //不能整除则无解
else {
ans=(temp＊c/b);
if (sumit(ans)==a) printf("1 %d\n",ans); //检测成功
else printf("0\n");
}
}
return 0;
}
1.1.4 部分测试数据和输出结果
测试数据
3 3 2
56 2 1
24 8 5
32 24 21
18 9 5
6 6 5
56 57 39
56 56 39
4 4 3
31 31 25
0 0 0
输出结果
1 2
1 28
1 15
0
1 10
1 5
0
1 39
1 3
1 25