原题来自GDOI2007谁是天才,但找不到链接了
描述
这天周航遇到了靳泽旭。
周航：“我是天才！”
靳泽旭：“你为什么是天才？”
周航：“你随便告诉我一个数字，我立即可以算出它所有约数之和，以及所有约数的倒数和！”
靳泽旭：“换过来，我告诉你一个数的所有约数（包括1和该数本身）的和以及约数的倒数之和，你是天才你应该立即能推出这个数是什么！”
周航被难倒了！
现在，这个难倒了天才的题目就交到你手上了。
输入格式
输入文件包含多组测试数据(最多有\(3000\)组测试数据)。
每组测试数据有三个正整数\(A\),\(B_1\)和\(B_2\),\((1\le A,B_1,B_2\le 10^9)\),其中A为C的约数和，而对于\(C\)的所有倒数之和\(B\)，为避免精度误差，以分数\(\frac{B_1}{B_2}\)的形式给出。
输入文件以一行0 0 0 结束。
输出格式
对于输入的每一组数据，输出一行。该行的第一个整数N是所有满足条件的不同的C的个数。其后按照从小到大的顺序输出N个数，为所有满足条件的C。相邻两个整数之间用空格隔开，行末不要有空格。
样例输入
18 9 5
1 1 2
1 1 1
0 0 0样例输出
1 10
0
1 1思路
首先\(CDCQ\)有个不用数论的方法
首先对于一个数\(a\)如果\(b\)是他的约数，则\(\frac{a}{b}\)也一定是它的约数
所以\(A = a_1+\frac{c}{a_1}+a_2+\frac{c}{a_2}+\cdots+a_n+\frac{c}{a_n}\)
并且\(B = \frac{1}{a_1}+\frac{a_1}{c}+\frac{1}{a_2}+\frac{a_2}{c}+\cdots+\frac{1}{a_n}+\frac{a_n}{c}\)
然后\(B\times C=\frac{c}{a_1}+a_1+\frac{c}{a_2}+a_2+\cdots+\frac{c}{a_n}+a_n=A\)
我们就得到这样一个等式\(B\times C = A \Rightarrow C = \frac{A}{B} = \frac{A\times B_2}{B_1}\)
这样我们就得到了答案\(C\)
但这个答案一定正确么? 不一定吧
比如2 2 2这样一组数据，我们得到\(C = 2\),但是\(2\)的约数和应该是\(1+2 = 3\)
所以我们应该在验证一下答案时候正确
我们把\(C\)质因数分解成\(C = p_{1}^{a_1}\times p_{2}^{a_2}\times\cdots\times p_{n}^{a_n}\)
则\(A = (1+p_{1}^{1}+p_{1}^{2}+\cdots+p_{1}^{a_1})\times(1+p_{2}^{1}+p_{2}^{2}+\cdots+p_{2}^{a_2})\times\cdots\times(1+p_{n}^{1}+p_{n}^{2}+\cdots+p_{n}^{a_n})\)
用这种方式验证一下答案是否正确即可
coding
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1100;
LL a,b1,b2;
LL p[N],k[N],cur;
inline LL read()
{
register LL x = 0;
register char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9')
{
x = (x<<3)+(x<<1) + ch-'0';
ch = getchar();
}
return x;
}
inline void divde(LL x)
{
cur = 0; memset(k,0,sizeof(k));
for(register int i = 2;i * i <= x;i ++)
{
if(x%i) continue;
p[++cur] = i;
while(x % i == 0) x/= i,k[cur]++;
}
if(x == 1) return ;
p[++cur] = x; k[cur] = 1;
return ;
}
inline bool check(LL x)
{
divde(x);
register LL sum = 1;
for(register int i = 1;i <= cur; i ++)
{
register LL s1 = 1,s2 = 0;
k[i] ++;
while(k[i]--) s2 += s1,s1 *= p[i];
sum *= s2;
}
return sum == a;
}
int main()
{
a = read(); b1 = read(); b2 = read();
while(a && b1 && b2)
{
if(a * b2 % b1 || b1 < b2)
{
puts("0");
a = read(); b1 = read(); b2 = read();
continue;
}
LL ans = a * b2 / b1;
if(check(ans)) printf("1 %lld\n",ans);
else puts("0");
a = read(); b1 = read(); b2 = read();
}
return 0;
}