首页 > 代码库 > 51nod 算法马拉松17 解题报告
51nod 算法马拉松17 解题报告
B题（数学题：
问(1+sqrt(2)) ^n 能否分解成 sqrt(m) +sqrt(m-1)的形式
如果可以 输出 m%1e9+7 否则 输出no n<=1e18
刚看题没思路 暴力一下吧 发现根本没有no的情况 那么就好办多了
所求的值序列为 1, 2, 9, 50, 289, 1682, 9801, 57122, 332929, 1940450, 11309769
设(1+sqrt(2)) ^n为 A_n+B_n*sqrt(2) ,则：
A_n = A_(n-1)+2*B_(n-1)
A_n = A_(n-1)+B_(n-1)
那么所求值序列显然为A_n*A_n+(n&1)
我们需要求这个A_n 暴力肯定不行，看到上面的递推式可以想到矩阵快速幂---
这个矩阵构造也非常简单
/*
1 2 A_n A_(n+1)
* =
1 1 B_n B_(n+1)
*/
然后注意下细节
#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <vector>#include <cstring>#include <set>#include <map>using namespace std;typedef long long ll;inline void r(ll&num){ num=0;ll f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘)num=num*10+ch-‘0‘,ch=getchar(); num*=f;}inline void r(int &num){ num=0;int f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘)num=num*10+ch-‘0‘,ch=getchar(); num*=f;}const long long N = 2;const long long M = 1e9+7;struct Matr{ long long line; long long a[N+1][N+1]; Matr(){ line=2; a[0][0] = 1; a[0][1] = 2; a[1][0] = 1; a[1][1] = 1; }};Matr isit(Matr x,long long c) //矩阵初始化{ for(long long i=0;i<N;i++) for(long long j=0;j<N;j++) x.a[i][j]=c; return x;}Matr Matlab(Matr x,Matr s) //矩阵乘法{ Matr ans; ans.line = x.line; ans=isit(ans,0); for(long long i=0;i<x.line;i++) { for(long long j=0;j<x.line;j++) { for(long long k=0;k<s.line;k++) { ans.a[i][j] = (ans.a[i][j]+x.a[i][k]*s.a[k][j])%M; ans.a[i][j]=(ans.a[i][j]+M)%M; } } } return ans;}long long Fast_Matrix(Matr tmp,long long n){ if(n==1) return 1; if(n==0) return 1; if(n==2) return 3; n--; Matr ans,ch; ans.line = 2; ans.a[0][0] = 1; ans.a[0][1] = 0; ans.a[1][0] = 1; ans.a[1][1] = 0; while(n>0) { if(n%2) { ans=Matlab(ans,tmp); } tmp=Matlab(tmp,tmp); n/=2; } return (ans.a[0][0]+ans.a[0][1])%M;}int main(){ Matr T; long long n; cin>>n; long long x = Fast_Matrix(T,n); cout<<(x*x+(n&1))%M<<endl; return 0;}
51nod 算法马拉松17 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。