jimore

用户名：uq_30465888842

访问量：9720

签　名：

Don't let the dream just be a dream!!!

等　　级
排　　名	176
经　　验	6840
参赛次数	29
文章发表	63
年　　龄	0
在职情况	学生
学　　校	四川农业大学
专　　业	计算机科学与技术

　　自我简介：

目标院校：上海交通大学

TA的其他文章

人工智能之猫狗分类优化（英文版）
浏览：211

cnn卷积神经网络(史上最容易理解版)
浏览：588

one-shot learning
浏览：198

你可能喜欢

C语言程序设计教程（第三版）课后习题11.8 （C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

佩尔方程——模板题

　　作者: jimore　　　　发表时间：2022-07-21 19:05:46 浏览：220　|　评论：0　

原题链接：Happiness Hotel

# Pell Equation

#### 题意分析：

给定小于 $$1000$$ 的正整数 $$k$$ , 存在正整数 $$x$$ , $$d$$ ，使得 $$kx^2+1=d^2$$ ，求满足条件最小的 $$d$$ 。将这个等式调换下位置，就是 $$d^2-kx^2=1$$ ，显然是一个佩尔方程（ $$pell$$ 方程， $$pell$$ $$equation$$ ）。所以其实这道题就是求佩尔方程的最小特解。

直接上求解 $$pell$$ $$equation$$ 的代码模板

#include <bits/stdc++.h>
    #define inf 0x3f3f3f3f
    #define ms(a,b) memset(a,b,sizeof(a))
    using namespace std;
    typedef long long ll;
     
    int can[1005] = {0};
    int a[10005][605]= {0};
    int x[6005], y[6005], t[6005];
    int h1,h2;
    int bb, ee, xx, yy, c, n;
     
    void Pell(int ji,int many,int ma,int kk)
    {
        if (ji < kk)
            Pell(ji + 1, a[ma][(ji-1)%a[ma][600]+1], ma, kk);
        else
        {
            h1 = 1;
            h2 = 1;
            x[1] = many;
            y[1] = 1;
            return;
        }
        for (int i = 1; i <= h1; i++)
            t[i] = x[i];
        for (int i = 1; i <= h2; i++)
            x[i] = y[i];
        for (int i = 1; i <= h1; i++)
            y[i] = t[i];
        c = h1;
        h1 = h2;
        h2 = c;
        for (int i = 1; i <= h2; i++)
            if (i <= h1)
                x[i] += many * y[i];
            else
                x[i] = many * y[i];
        if (h2 > h1)
            h1 = h2;
        for (int i = 1; i < h1; i++)
            if (x[i] >= 10)
            {
                x[i+1] += x[i] / 10;
                x[i] %= 10;
            }
        while(x[h1] >= 10)
        {
            x[h1+1] = x[h1] / 10;
            x[h1] %= 10;
            h1++;
        }
        x[0] = h1;
    }
     
    void solve()
    {
        int i, j;
        for (j = 1; j <= 31; j++)
            can[j*j] = true;
        for(i = 1; i <= 1000; i++)
        {
            if(!can[i])
            {
                a[i][600]=1;
                bb = 1;
                ee = (int)sqrt((double)i);
                a[i][0] = ee;
                ee =- ee;
                xx = bb;
                yy = ee;
                xx =- yy;
                yy = i - yy * yy;
                n=0;
                while((xx - yy) * (xx - yy) < i || xx >= 0)
                {
                    xx -= yy;
                    n++;
                }
                a[i][1] = n;
                c = xx, xx = yy, yy = c;
                while(xx != bb || yy != ee)
                {
                    a[i][600]++;
                    c = xx;
                    xx =- yy;
                    yy = i - yy * yy;
                    yy = yy / c;
                    n = 0;
                    while ((xx - yy) * (xx - yy) < i || xx >= 0)
                    {
                        xx -= yy;
                        n++;
                    }
                    a[i][a[i][600]] = n;
                    c = xx, xx = yy, yy = c;
                }
            }
        }
    }
     
    int main()
    {
        int k;
        solve();
        while(scanf("%d",&k)!=EOF)///ans^2 = k * n ^ 2 + 1,求ans的最小值(k <= 1000)
        {
            if(!can[k])
            {
                if(a[k][600] % 2)
                    Pell(1, a[k][0], k, a[k][600]*2);
                else
                    Pell(1, a[k][0], k, a[k][600]);
                for (int j = x[0]; j >= 1; j--)
                    printf("%d",x[j]);
                printf("\n");
            }
            else
                printf("no solution\n");
        }
        return 0;
    }

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

jimore

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.8 （C++代码）

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C++代码）

字符串的输入输出处理（C语言代码）

佩尔方程——模板题

评论区

精彩推荐

C语言训练-排序问题<2> （C++代码）（sort函数）

C语言训练-舍罕王的失算（C++代码）（都给答案了还算什么）

简单的a+b （C语言代码）

C语言训练-最大数问题（C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

关于C语言变量位置的问题

文科生的悲哀（C语言代码）

1013题解

jimore

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.8 （C++代码）

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C++代码）

字符串的输入输出处理 （C语言代码）

佩尔方程——模板题

评论区

精彩推荐

C语言训练-排序问题<2> （C++代码）（sort函数）

C语言训练-舍罕王的失算 （C++代码）（都给答案了还算什么）

简单的a+b （C语言代码）

C语言训练-最大数问题 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

关于C语言变量位置的问题

文科生的悲哀 （C语言代码）

1013题解

C二级辅导-阶乘数列（C语言代码）

字符串的输入输出处理（C语言代码）

　　评论区

C语言训练-舍罕王的失算（C++代码）（都给答案了还算什么）

C语言训练-最大数问题（C语言代码）

文科生的悲哀（C语言代码）