佩尔方程x*x-d*y*y=1,当d不为完全平方数时,有无数个解,并且知道一个解可以推其他解。 如果d为完全平方数时,可知佩尔方程无解。

假设(x0,y0)是最小正整数解。

则:

xn=xn-1*x0+d*yn-1*y0

yn=xn-1*y0+yn-1*x0

证明只需代入。 如果忘记公式可以自己用(x0*x0-d*y0*y0)*(x1*x1-d*y1*y1)=1 推。

这样只要暴力求出最小特解,就可以用快速幂求出任意第K个解。

Street Numbers
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 2813   Accepted: 1568

Description

A computer programmer lives in a street with houses numbered consecutively (from 1) down one side of the street. Every evening she walks her dog by leaving her house and randomly turning left or right and walking to the end of the street and back. One night she adds up the street numbers of the houses she passes (excluding her own). The next time she walks the other way she repeats this and finds, to her astonishment, that the two sums are the same. Although this is determined in part by her house number and in part by the number of houses in the street, she nevertheless feels that this is a desirable property for her house to have and decides that all her subsequent houses should exhibit it. 
Write a program to find pairs of numbers that satisfy this condition. To start your list the first two pairs are: (house number, last number):

         6         8

35 49

Input

There is no input for this program.

Output

Output will consist of 10 lines each containing a pair of numbers, in increasing order with the last number, each printed right justified in a field of width 10 (as shown above).

Sample Input


Sample Output

         6         8
35 49

这题可以得到佩尔方程s*s-8*t*t=1 ,s=2n+1,t=x (n表示总长,x表示取的n中某个位置)

s0=3,t0=1 然后就很好弄了

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std; int main(int argc, const char * argv[]) {
long long s0=;
long long t0=;
long long s1=;
long long t1=;
for(int i=;i<=;i++)
{
long long s,t;
s=s1*s0+*t1*t0;
t=t1*s0+t0*s1;
s1=s;
t1=t;
printf("%10lld%10lld\n",t,(s-)/);
//cout<<t<<" "<<(s-1)/2<<endl;
}
return ;
}

这题用暴力然后打表也是可以0MS过的。

最新文章

  1. 编写高质量代码:改善Java程序的151个建议(第2章:基本类型___建议26~30)
  2. Last time, I wrote a pager, but now it seems this no longer has use, so I want to paste it here.
  3. 给li设置float浮动属性之后,无法撑开外层ul的问题。
  4. python基础学习二——第二天
  5. COM调用 &ndash; VB、PB
  6. 转!! Java中如何遍历Map对象的4种方法
  7. Matla学习:figure+axes+plot
  8. uva331 - Mapping the Swaps
  9. 【.Net--资料】
  10. 对CLR异常和状态管理的一点理解
  11. 在List中找出最大值的两种方法
  12. 单片微机原理P0:80C51结构原理
  13. 老李推荐:第8章2节《MonkeyRunner源码剖析》MonkeyRunner启动运行过程-解析处理命令行参数 2
  14. java34
  15. 常见问题1:默认div隐藏,点击按钮时出现,再点击时隐藏。
  16. rabbitmq集群部署及配置
  17. c# 继承与多种状态
  18. snort安装使用教程(CentOS6.5)
  19. Python使用SMTP发送邮件(163,yeah等网易邮箱已测试可以)
  20. VS 远程调试 Azure Web App

热门文章

  1. hdu1008(c++)
  2. 通过Linux定时任务实现定时轮询数据库及发送Http请求
  3. 在自己的网站上使用RSS订阅功能
  4. Jenkins 安装卡住不动的解决方案
  5. Angular 学习笔记——filter
  6. 编程算法 - 食物链 并查集 代码(C)
  7. CocoaPods安装及相关命令
  8. flask的分页功能
  9. pomodoro源码
  10. 字典转模型的过程中,空值和id特殊字符的处理