求助，用递归的方法求Pell's equation p^2-2q^2=1的前50对解 - 编程论坛

#2

JabinZ2020-05-30 21:01

你用 count==10 限制了只处理10对数据，当然不会出现50个

程序代码：

printf("(%d,%d) ",p,q);
// 改为
printf("(%lld,%lld) ",p,q);

[此贴子已经被作者于2020-5-30 21:10编辑过]

#3

rjsp2020-05-30 21:07

编译你的代码报错：
printf("(%d,%d) ",p,q);
warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int'

另外，你题目中说50个，怎么代码中却是 if(count==10) break ？

#4

楚子航9922020-05-30 21:13

回复 2楼 JabinZ

您好，改完之后还是出现不了50个

#5

JabinZ2020-05-30 21:35

我现在有几个问题

1. 你的这个方程式的解，到后面数大概多大，你自己知道么？（找到第12个解，就已经9位数了，那按照你写的这个方法，要循环多少次才能找到50个答案，你需要等多久？）
2. 以你目前的方法，根本不要考虑改成递归，压栈会死掉的

#6

楚子航9922020-05-30 21:36

回复 5楼 JabinZ

所以我的目的就是来论坛问问大佬们，用什么方法做，我知道我这个算法不行的，所以来请教下

#7

rjsp2020-05-30 22:05

路过，纯吃瓜群众，我只是想看看 long long int 能不能容得下前50个解。

程序代码：

int main( void )
{
    typedef unsigned long long TYPE;

    TYPE d = 2;
    TYPE x1=3, y1=2;
    TYPE xn=x1, yn=y1;

    for( size_t i=0; i!=50; ++i )
    {
        printf( "%zu: %llu, %llu\n", i+1, xn, yn );

        if( xn*x1/x1!=xn || d*yn*y1/y1/yn!=d || xn*x1+d*yn*y1<xn*x1 )
        {
            puts( "overflow" );
            break;
        }

        TYPE x = xn*x1 + d*yn*y1;
        TYPE y = xn*y1 + yn*x1;
        xn=x, yn=y;
    }
}

结果是只能容纳前25组解，输出结果是

1: 3, 2
……
25: 6882627592338442563, 4866752642924153522
overflow

然后我将 unsigned long long 换成非标准的 __uint128_t，正巧能容纳下第50组，接下来就溢出了。

#8

fulltimelink2020-05-30 22:37

p只可能是奇数，所以p可以+=2
话说1 0算一对解么

#9

forever742020-05-30 22:44

以下是引用fulltimelink在2020-5-30 22:37:38的发言：

p只可能是奇数，所以p可以+=2
话说1 0算一对解么

玩数论的时候一般对0有歧视，只玩正整数

，所以不算。

#10

fulltimelink2020-05-31 07:40

回复 9楼 forever74

了解了

#11

楚子航9922020-05-31 19:12

回复 7楼 rjsp

#include<stdio.h>
#define M 10000

void multiply(int x[], int y, int z[]) {
    int i, temp, b = 0;
    for (i = M - 1; i >= 0; i--)
    {
        temp = x[i] * y + b;
        z[i] = temp % 10;
        b = temp / 10;
    }
}

void add(int a[], int b[], int c[]) {
    int i, temp, k = 0;
    for (i = M - 1; i >= 0; i--) {
        temp = a[i] + b[i] + k;
        c[i] = temp % 10;
        k = temp / 10;
    }

}

void copy(int x[], int y[]) {
    int i, j;
    for (i = 0; i < M; i++) {
        if (x[i] > 0) {
            j = i;
            break;
        }

    }
    for (i = j; i < M; i++) {
        y[i] = x[i];
    }
}

void pell(int i, int a[], int b[], int a1[], int a2[], int b1[], int b2[]) {
    int j, m, n;
    if (i == 0) { printf("end"); }
    else {
        multiply(a, 3, a2);
        multiply(b, 4, b2);
        add(a2, b2, a1);
        multiply(a, 2, a2);
        multiply(b, 3, b2);
        add(a2, b2, b1);
        copy(a1, a);
        copy(b1, b);
        for (j = 0; j < M; j++) {
            if (a1[j] > 0)
            {
                m = j;
                break;
            }
        }
        printf("(");
        for (n = m; n < M; n++)
            printf("%d", a1[n]);
        printf(", ");
        for (j = 0; j < M; j++)
        {
            if (b1[j] > 0)
            {
                m = j;
                break;
            }
        }
        for (n = m; n < M; n++)
            printf("%d", b1[n]);
        printf(")");
        printf("\n");
        pell(i - 1, a, b, a1, a2, b1, b2);
    }

}

int main() {
    int a[M] = { 0 }, b[M] = { 0 };
    a[M - 1] = 3;
    b[M - 1] = 2;
    int a1[M] = { 0 }, a2[M] = { 0 }, b1[M] = { 0 }, b2[M] = { 0 };
    printf("(p, q):\n");
    printf("(3, 2)\n");
    pell(49, a, b, a1, a2, b1, b2);
    fflush(stdin);
    getchar();
    return 0;
}
这个可以，秒出

#12

楚子航9922020-05-31 19:14

回复 9楼 forever74

#include<stdio.h>
#define M 10000

void multiply(int x[], int y, int z[]) {
    int i, temp, b = 0;
    for (i = M - 1; i >= 0; i--)
    {
        temp = x[i] * y + b;
        z[i] = temp % 10;
        b = temp / 10;
    }
}

void add(int a[], int b[], int c[]) {
    int i, temp, k = 0;
    for (i = M - 1; i >= 0; i--) {
        temp = a[i] + b[i] + k;
        c[i] = temp % 10;
        k = temp / 10;
    }

}

void copy(int x[], int y[]) {
    int i, j;
    for (i = 0; i < M; i++) {
        if (x[i] > 0) {
            j = i;
            break;
        }

    }
    for (i = j; i < M; i++) {
        y[i] = x[i];
    }
}

void pell(int i, int a[], int b[], int a1[], int a2[], int b1[], int b2[]) {
    int j, m, n;
    if (i == 0) { printf("end"); }
    else {
        multiply(a, 3, a2);
        multiply(b, 4, b2);
        add(a2, b2, a1);
        multiply(a, 2, a2);
        multiply(b, 3, b2);
        add(a2, b2, b1);
        copy(a1, a);
        copy(b1, b);
        for (j = 0; j < M; j++) {
            if (a1[j] > 0)
            {
                m = j;
                break;
            }
        }
        printf("(");
        for (n = m; n < M; n++)
            printf("%d", a1[n]);
        printf(", ");
        for (j = 0; j < M; j++)
        {
            if (b1[j] > 0)
            {
                m = j;
                break;
            }
        }
        for (n = m; n < M; n++)
            printf("%d", b1[n]);
        printf(")");
        printf("\n");
        pell(i - 1, a, b, a1, a2, b1, b2);
    }

}

int main() {
    int a[M] = { 0 }, b[M] = { 0 };
    a[M - 1] = 3;
    b[M - 1] = 2;
    int a1[M] = { 0 }, a2[M] = { 0 }, b1[M] = { 0 }, b2[M] = { 0 };
    printf("(p, q):\n");
    printf("(3, 2)\n");
    pell(49, a, b, a1, a2, b1, b2);
    fflush(stdin);
    getchar();
    return 0;
}
帮忙看下我这么编可以么