HDU 2256 Problem of Precision 数论矩阵快速幂
发布日期:2021-08-31 13:57:31 浏览次数:29 分类:技术文章

本文共 1696 字,大约阅读时间需要 5 分钟。

题目要求求出(√2+√3)2n的整数部分再mod 1024。

(√2+√3)2n=(5+2√6)n

如果直接计算,用double存值,当n很大的时候,精度损失会变大,无法得到想要的结果。

我们发现(5+2√6)n+(5-2√6)n是一个整数(2√6的奇数次幂总会正负抵消掉),并且(5-2√6)n是小于1的。所以我们就只需要求出S(n)-1即可。令

  An=(5+2√6)n;  Bn=(5-2√6)n.

  Sn=An+B    Sn为整数。

  Sn*((5+2√6)+(5-2√6))=Sn*10

  Sn*10=(5+2√6)n+1+(5-2√6)n+1+(5+2√6)n-1+(5-2√6)n-1

  Sn*10=Sn+1+Sn-1

  递推式:Sn=10*Sn-1-Sn-2

然后转化为矩阵快速幂求Sn

#include 
#include
#include
using namespace std;const int Mod=1024;const int N=2;struct Mat{ int mat[N][N];}a;Mat Multiply(Mat a, Mat b){ Mat c; memset(c.mat, 0, sizeof(c.mat)); for(int k = 0; k < 2; ++k) for(int i = 0; i < 2; ++i) if(a.mat[i][k]) for(int j = 0; j < 2; ++j) if(b.mat[k][j]) c.mat[i][j] = (c.mat[i][j] +a.mat[i][k] * b.mat[k][j])%Mod; return c;}Mat QuickPower(Mat a, int k){ Mat c; memset(c.mat,0,sizeof(c.mat)); for(int i = 0; i < 2; ++i) c.mat[i][i]=1; for(; k; k >>= 1) { if(k&1) c = Multiply(c,a); a = Multiply(a,a); } return c;}void InitMat(Mat &A){ A.mat[0][0]=10; A.mat[0][1]=-1; A.mat[1][0]=1; A.mat[1][1]=0;}int main(){ //freopen("in.txt","r",stdin); int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); if(n==1) printf("9\n"); else if(n==2) printf("97\n"); else { InitMat(a); a=QuickPower(a,n-2); int ans=(a.mat[0][0]*98+a.mat[0][1]*10-1)%1024; //我们求的是S[n]-1 while(ans<0) ans+=1024; printf("%d\n",ans); } } return 0;}

 

转载于:https://www.cnblogs.com/pach/p/5991251.html

转载地址:https://blog.csdn.net/weixin_34077371/article/details/93099938 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:POJ 1681 高斯消元 枚举自由变元
下一篇:SQL注入***防御深层思考

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年03月19日 04时16分12秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php使用redis持久化,redis如何持久化 2019-04-21
php7.1解压包安装,【Swoole】php7.1安装swoole扩展 2019-04-21
linux centos删除安装的包,CentOS yum认为已删除的软件包仍在安装中 2019-04-21
酒店管理系统c语言带注释,酒店管理系统--C语言版.pdf 2019-04-21
c语言 实现sizeof功能,C语言简单实现sizeof功能代码 2019-04-21
c语言sin函数近似值,用泰勒公式求sin(x)的近似值 2019-04-21
c 语言登录系统源代码,c语言源代码---------------个人图书管理系统 2019-04-21
android线程通信方式,Android 主线程和子线程通信问题 2019-04-21
cps1 cps2 android,图文教程:CPS1和CPS2模拟器使用 2019-04-21
在线设计 html5 表单,html5注册表单制作-表单制作-小程序表单制作 2019-04-21
android小闹钟课程设计,《小闹钟》教学设计 2019-04-21
mysql文件系统_MySQL文件系统先睹为快(1) 2019-04-21
nums在python_程序找到一对(i,j),其中nums [i] + nums [j] +(i -j)在Python中最大化?... 2019-04-21
jquery后台内容管理_教育平台项目后台管理系统:课程内容模块 2019-04-21
grouping函数 mysql_sql聚合函数有哪些 2019-04-21
python os.walk如何不遍历隐藏文件_python 获取文件下所有文件或目录os.walk()的实例... 2019-04-21
python 股票估值_【中金固收·固收+】隐藏价值的角落:限售股AAP估值及Python实现方法(上)... 2019-04-21
java文档生成_Java文档自动生成 2019-04-21
java 共享目录_java 操作windows 共享目录方法介绍 2019-04-21
java 监控 宕机_JAVA监测tomcat是否宕机,控制重启 2019-04-21