首页 > 代码库 > Uva 138-Street Numbers(佩尔方程)
Uva 138-Street Numbers(佩尔方程)
题目链接:点击打开链接
题意: 一条街上有n个房子编号从1到n 设某人的房子编号为k 求满足 1+2+3+..(k-1)=(k+1)+...+n 的10组n,k值
两边求和化简得 n^2+n-2k^2=0; 两边同乘4 -> 4n^2+4n+1-8k^2=1; -> (2n+1)^2-2(2k)^2=1;
令 x=2n+1 y=2k 得 x^2-2y^2=1; 形如 x^2-ny^2=1 (n为任意正整数) 的方程称为佩尔方程,很容易求出其最小解 (x0,y0)
然后 xi=x0*x(i-1)+n*y0*y(i-1)
yi=y0*x(i-1)+x0*y(i-1) ;递推可得方程所有解
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 10000002 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 10000007 #define pp pair<int,int> #define ull unsigned long long using namespace std; int main() { int x[11]={3},y[11]={2}; for(int i=1;i<=10;i++){ x[i]=x[i-1]*x[0]+2*y[i-1]*y[0]; y[i]=x[i-1]*y[0]+y[i-1]*x[0]; int n=(x[i]-1)/2,k=y[i]/2; printf("%10d%10d\n",k,n); } return 0; }
Uva 138-Street Numbers(佩尔方程)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。