Pell函数c语言,c语言fill函数
求解一个佩尔方程
方程没有10亿以内的解，手动计算应该是行不通的
成都创新互联-专业网站定制、快速模板网站建设、高性价比马山网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式马山网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖马山地区。费用合理售后完善，十余年实体公司更值得信赖。
我写了一个程序，计算出方程的一组特解:
x=379516400906811930638014896080
y=12055735790331359447442538767
算法是求√991的渐进连分数h0/k0,h1/k1...h(l-1)/k(l-1),l是连分数的最小正周期，若l是偶数，则h(l-1)和k(l-1)就是pell方程的一组特解，否则h(2l - 1)和k(2l- 1)是方程的一组特解。证明可以在任何一本数论书上找到，不再赘述，也可以参考wiki百科的pell方程条目
程序附在后面，C++写的，任何一个windows平台下的C++编译器都可以编译(VC++,DEVCPP等等),涉及到大整数的运算比较麻烦，用matlab写起来会更简单
程序清单:
#include stdio.h
#include stdlib.h
#include memory.h
#include math.h
#define LEN 200
#define BASE 10000000 //大整数用10^7进制来计算
typedef __int64 INT;
struct BIG //大整数结构定义，整数每7位拼成一个int64,这样加减乘计算耗时较少
{
INT a[LEN];//存放大整数的数组
int len; //标记大整数的长度，不能超过200
}h[3],k[3];
INT a[1 14],c[1 14],q[1 14];
/*实际是计算:
h[i] = n*h[i - 1] + h[i - 2];
k[i] = n*k[i - 1] + k[i - 2];
这是连分数的递推形式
*/
void go(INT n)
{
int i;
for(i = 0;i h[1].len;i++)
h[2].a[i] = h[1].a[i] * n + h[0].a[i];
for(i = 0;i h[1].len;i++)
h[2].a[i + 1] += h[2].a[i] / BASE,h[2].a[i] %= BASE;
if(h[2].a[h[2].len])
h[2].len++;
for(i = 0;i k[1].len;i++)
k[2].a[i] = k[1].a[i] * n + k[0].a[i];
for(i = 0;i k[1].len;i++)
k[2].a[i + 1] += k[2].a[i] / BASE,k[2].a[i] %= BASE;
if(k[2].a[k[2].len])
k[2].len++;
for(i = 0;i 2;i++)
h[i] = h[i + 1],k[i] = k[i + 1];
}
void print(BIG a) //把大整数输出
{
int i;
printf("%I64d",a.a[a.len - 1]);
for(i = a.len - 2;i = 0;i--)
printf("%07I64d",a.a[i]);
}
int main()
{
int i,j,len;
bool use = false;
c[0] = 0,q[0] = 1,a[0] = 31;
for(i = 1;;i++) //寻找连分数循环节，j-i是最小循环周期
{
c[i] = a[i - 1] * q[i - 1] - c[i - 1];
q[i] = (991 - c[i] * c[i])/q[i - 1];
a[i] = (a[0] + c[i])/q[i];
if(!use)
{
for(j = 0;j i;j++)
{
if(c[i] == c[j] a[i] == a[j] q[i] == q[j])
{
len = i - j;
break;
}
}
if(j i)
break;
}
}
if(len 1) //循环节长度是奇数，长度要乘以2
len = 1;
for(i = 0;i 3;i++)
{
memset(h[i].a,0,sizeof(h[i].a));
memset(k[i].a,0,sizeof(k[i].a));
h[i].len = k[i].len = 0;
}
h[0].a[0] = a[0],h[0].len = 1;
h[1].a[0] = a[0] * a[1] + 1;
h[1].len = 1;
k[0].a[0] = 1,k[0].len = 1;
k[1].a[0] = a[1],k[1].len = 1;
for(i = 2;i len;i++)
go(a[i]);
printf("x = ");
print(h[2]);
printf(" ");
printf("y = ");
print(k[2]);
printf("\n");
system("PAUSE");
return 0;
}
佩尔方程解的证明
佩尔方程
Pell方程，由费马提出，但后来欧拉误记为佩尔提出，并写入他的著作中。后人多称佩尔方程。沿续至今。
基本内容
设d是正整数，且d不含平方因子。
下面的不定方程称为佩尔（Pell）方程：
x^2-dy^2=1
求正整数解(x,y).
这是初等数论中最经典的内容之一。
假设(x_0,y_0)是一个最小解， 那么所有的解可写为
x_n+y_n*(d)^0.5=(x_0+y_0*(d)^0.5)^(n+1)
佩尔方程与连分数，二次型，代数数域等等都有密切联系。
在一般的函数域上，我们也有类似的佩尔方程， 它和向量丛的稳定性有着微妙的关系。
简单C语言求大神
#includestdio.h
#includestring.h
int main()
{
int n = 0, m = 0;
int i = 0,j = 0;
char a[81] = "";
char *p = NULL;
while(EOF !=scanf("%d",n))
{
if (n 1 || n 1000)
continue;
break;
}
while (i n)
{
scanf("%d %s",m,a);
p = a + m;
*(p - 1) = '\0';
printf("%d %s%s\n",++i,a,p);
}
return 0;
}
C语言，数据结构，
#include stdio.h
#include "stdlib.h"
int main(void){
int n,i,j,k,t,r,*p;
printf("Input n(int n0)...\nn=");
if(scanf("%d",n)!=1 || n1){
printf("Input error, exit...\n");
return 0;
}
if((p=(int *)malloc(sizeof(int)*n))==NULL){
printf("Application memory failure...\n");
return 0;
}
printf("Input k(int 0k100000)...\n");
i=-1;
while(++in){
while(scanf("%d",k)!=1 || k1 || k99999){
printf("Error, redo:");
fflush(stdin);
}
p[i]=k;
}
for(t=0;tn;t++)
if(p[t]2){
for(i=1,j=k=2;kp[t];k++)
r=((i%=32767)+((j%=32767)*2)%32767)%32767,i=j,j=r;
printf("%d\n",r);
}
else
printf("%d\n",p[t]);
free(p);
printf("\n");
return 0;
}
pell方程通解
佩尔方程是一种不定二次方程。
古希腊数学家在计算2的平方根时，尝试使用了这类方程中的一个，婆罗摩笈多(Brahmagupta)对佩尔方程的研究进行了最早的贡献 ，佩尔方程和欧几里德算法一起使用，可计算一个正整数的平方根的近似值 。由于欧拉最早把此类方程称为佩尔方程，所以就有了这个名词了。实际上，数学家费马深入研究了这类方程，拉格朗日给出了解决方案 。所以在数学界，它也被称为“佩尔-费马方程”。
设d是正整数，且非平方数。
下面的不定方程称为佩尔（Pell）方程：
佩尔方程
佩尔方程
....(1)
(1)一定有无穷多组正整数解
这是初等数论中最经典的内容之一。
佩尔方程
佩尔方程
佩尔方程
佩尔方程
假设( )是①中使 最小的正整数解（称(1)的基本解）， 那么①的所有的正整数解可写为
x_n=1/2[(x_1+y_1d^0.5)^n+(x_1-y_1d^0.5)^n]
y_n=1/(2d^0.5)[(x_1+y_1d^0.5)^n-(x_1-y_1d^0.5)^n]
∴x_n+y_n*(d)^0.5=(x_0+y_0d^0.5)^(n+1)
且不难导出x_n,y_n满足的线性递推关系
x_n=2x_1x_(n-1)-x_(n-2)
y_n=2x_1y_(n-1)-y_(n-2)
佩尔方程与连分数，二次型，代数数域等等都有密切联系。
在一般的函数域上，我们也有类似的佩尔方程， 它和向量丛的稳定性有着微妙的关系。
以上的公式就是Pell方程的一般形态
佩尔方程通解
d不为完全平方数时时存在无穷多个解
解的存在性证明：
佩尔方程
佩尔方程
佩尔方程
佩尔方程
(1) 首先证明存在无穷多个正整数 满足 .
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
佩尔方程
记 = ，考察集合 ，显然对于任意正整数Q1，均存在 满足 （事实上，此集合中每个元数都在(0,1)之内 . 作区间 、 、 、 ，那么当 从0取到Q时，由抽屉原理即知）
佩尔方程
佩尔方程
于是 ，
佩尔方程
佩尔方程
即 .
佩尔方程
佩尔方程
让Q从小到大取遍所有正整数，就可得到无穷多组正整数 .
文章题目：Pell函数c语言,c语言fill函数
文章位置：http://scyanting.com/article/hsgcci.html
