pell方程的c++求解代码

pell方程是一个形式为\( x^2 - Dy^2 = 1 \)的二次同余方程，其中D是一个非平方整数。在C++中，可以使用扩展欧几里得算法来解决这类方程。下面是一个简单的pell方程求解的示例代码：

#include <iostream>
#include <cmath>

// 扩展欧几里得算法
std::pair<int, int> extendedEuclid(int a, int b) {
    if (b == 0) {
        return {a, 1, 0};
    } else {
        auto [d, x, y] = extendedEuclid(b, a % b);
        return {d, y, x - (a / b) * y};
    }
}

// 解决pell方程
int solvePellEquation(int D) {
    int x = 0, y = 1; // 初始猜测值
    while (true) {
        int q = x / sqrt(D); // 计算x除以根号下D的结果的整数部分
        int nextX = q * sqrt(D) + y;
        int nextY = x - q * y;

        if (nextX * nextX - D * nextY * nextY == 1) {
            break;
        }

        x = nextX;
        y = nextY;
    }
    return nextX;
}

int main() {
    int D = 7; // 替换为你需要计算的D值
    int solution = solvePellEquation(D);
    std::cout << "解方程 x^2 - " << D << "*y^2 = 1 的解为 x=" << solution << ", y=" << y << std::endl;
    return 0;
}

这个程序会找到满足\( x^2 - D*y^2 = 1 \)的一个解。注意，对于每个D，pell方程可能有无穷多个解，这里只找到了一个。