求C++求等式问题
来源:百度知道 编辑:UC知道 时间:2024/05/23 12:56:31
第一行输入一个正整数M,下面有M行,每一行都是一个正整数N.
输出共M行,每行都是方程解的个数.
Sample Input
2
1
2
Sample Output
1
3
提示:
当N=2时,共有三个解 X=4,Y=4; X=3,Y=6;X=6,Y=3.
上面的是ACM的问题
下面是我自己写的,不过提交上后是错的,求高手看看我哪里不对
#include<stdio.h>
int main(void)
{
int m,n,y,t,f,count=0,i;
while(scanf("%d",&m)==1){
for(i=1;i<=m;i++){
scanf("%d",&n);
y=n+1;
t=n*y;
if(n==1)count++;
else count=count+2;
while(y<t){
y++;
if(n*y%(y-n)==0){
f=n*y/(y-n);
if(f==y)
count++;
else count=count+2;
t=f;}
}
printf("%d\n",count);
count=0;
}}
return 0;
}
while(y<t){ 这里t是 n^2 + n
之前你考虑了 y = n+1的情况, 接着你从 y=n+2一直算到了 y = n^2 + n 。 所以 else count=count+2; 这句就有问题了。 你之前是考虑到 X Y调换是两种情况,但是其实 y 取n+1的时候正好是X取n^2+n的情况,你已经是重复算过了。 所以要么你别搞什么 count +2 ,要么你就贯彻想法, 只算y 比较小的一半,就是 y < 2n的情况。
另外, 按你这个算法即使是只算 n+1到 2n这么多种情况还是要超时的。 所以必须先做一些数学处理。
1/X + 1/Y = 1/N => YN + XN = XY => Y(X-N) = XN = (X-N)N + N*N
=> Y = N + N*N/(X-N) 也就是说, X-N是N*N的因数。所以只要求N的质因数, 得到质因数次数分别位 n1, n2, n3, ....ni 这样 N*N的质因数次数就是 2n1, 2n2, 2n3, ... 2ni ,这样 X-N 就有 (2n1+1)(2n2+1)(2n3+1) ...(2ni+1) 这么多种选择, 结果就是这个乘积
while(y<t){ 这里t是 n^2 + n
之前你考虑了 y = n+1的情况, 接着你从 y=n+2一直算到了 y = n^2 + n 。 所以 else count=count+2; 这句就有问题了。 你之前是考虑到 X Y调换是两种情况,但是其实 y 取n+1的时候正好是X取n^2+n的情况,你已经是重复算过了。 所以要么你别搞什么 count +2 ,要么你就贯彻想法, 只算y 比较小的一半,就是 y < 2n的情况。
另外, 按你这个算法即使是只算 n+1到 2n这么多种情况还是要超时的。 所以必须先做一些数学处理。
1/X + 1/Y = 1/N => YN + XN = XY => Y(X-N) = XN = (X-N)N + N*N
=> Y = N + N*N/(X-N) 也就是说, X