- 注册时间
- 2021-11-19
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 8641
- 在线时间
- 小时
|
发表于 2024-1-10 09:07:58
|
显示全部楼层
用mathe的思路,来处理分母上的\(\sqrt{5}\)这个问题。
上pari的代码
- n=10^14 /*n次幂*/
- m=1234567891011 /*模*/
- c1=Mod(1/(2*x-1),x^2-x-1) /*(1+sqrt(5))/2=x1,故1/sqrt(5)=1/(2*x1-1)*/
- p1=Mod(Mod(1,m)*x,x^2-x-1)^n /*计算x1^n mod x^2-x-1 */
- c2=Mod(1/(2*x-1),x^2-x-1) /*(1-sqrt(5))/2=x2,故-1/sqrt(5)=1/(2*x2-1)*/
- p2=Mod(Mod(1,m)*x,x^2-x-1)^n /*计算x2^n mod x^2-x-1 */
- cp1=c1*p1 /*计算通项公式的第1部分(正根)*/
- cp2=c2*p2 /*计算通项公式的第2部分(负根)*/
复制代码
输出结果log
- GP/PARI CALCULATOR Version 2.15.4 (released)
- amd64 running mingw (x86-64/GMP-6.1.2 kernel) 64-bit version
- compiled: Jun 28 2023, gcc version 10-posix 20210110 (GCC)
- threading engine: single
- (readline v8.0 enabled, extended help enabled)
- Copyright (C) 2000-2022 The PARI Group
- PARI/GP is free software, covered by the GNU General Public License, and comes
- WITHOUT ANY WARRANTY WHATSOEVER.
- Type ? for help, \q to quit.
- Type ?18 for how to get moral (and possibly technical) support.
- parisize = 8000000, primelimit = 500000
- (09:01) gp > n=10^14
- %1 = 100000000000000
- (09:02) gp > m=1234567891011
- %2 = 1234567891011
- (09:02) gp > c1=Mod(1/(2*x-1),x^2-x-1)
- %3 = Mod(2/5*x - 1/5, x^2 - x - 1)
- (09:02) gp > p1=Mod(Mod(1,m)*x,x^2-x-1)^n
- %4 = Mod(Mod(921144120792, 1234567891011)*x + Mod(512884989226, 1234567891011), x^2 - x - 1)
- (09:02) gp > c2=Mod(1/(2*x-1),x^2-x-1)
- %5 = Mod(2/5*x - 1/5, x^2 - x - 1)
- (09:02) gp > p2=Mod(Mod(1,m)*x,x^2-x-1)^n
- %6 = Mod(Mod(921144120792, 1234567891011)*x + Mod(512884989226, 1234567891011), x^2 - x - 1)
- (09:02) gp > cp1=c1*p1
- %7 = Mod(Mod(636296398051, 1234567891011)*x + Mod(759707806876, 1234567891011), x^2 - x - 1)
- (09:02) gp > cp2=c2*p2
- %8 = Mod(Mod(636296398051, 1234567891011)*x + Mod(759707806876, 1234567891011), x^2 - x - 1)
复制代码
从上面的结果可以看出cp1为(此处的x为x1,也就是正根)
Mod(Mod(636296398051, 1234567891011)*x + Mod(759707806876, 1234567891011), x^2 - x - 1)
cp2也是(此处的x为x2,也就是负根)
Mod(Mod(636296398051, 1234567891011)*x + Mod(759707806876, 1234567891011), x^2 - x - 1)
而根据韦达定理x1+x2=1(x1与x2是x^2-x-1=0的两个根)
Mod(636296398051, 1234567891011)*x1 + Mod(759707806876, 1234567891011)+Mod(636296398051, 1234567891011)*x2 + Mod(759707806876, 1234567891011)
=Mod(636296398051, 1234567891011)*(x1+x2) + Mod(759707806876, 1234567891011)*2
=Mod(636296398051, 1234567891011)*1 + Mod(759707806876, 1234567891011)*2
=Mod(921144120792, 1234567891011) 这个就是我们需要的结果
|
|