关键词：
题目传送门：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1537
神犇题解传送门：http://blog.csdn.net/qingshui23/article/details/52350523
证明好巧妙，给跪OTZ
题目的式子：$ {left( {1{ m{ + }}sqrt 2 } ight)^{ m{n}}} $，设其乘开之后为 $ { m{a + b}}sqrt 2 $
考虑相对的式子：$ {left( {1{ m{ - }}sqrt 2 } ight)^{ m{n}}} $,则乘开后为 $ { m{a + b}}sqrt 2 $
两式相乘，得到 $ {( - 1)^n} = {a^2} - 2{b^2} $
分奇偶讨论，如果n为偶数，则当 $ m = {a^2} $, $ m - 1 = {a^2} - 1 = 2{b^2} $,$ sqrt m + sqrt {m - 1} = a + bsqrt 2 $
n为奇数时同理，当 $ m = {a^2} + 1 = 2{b^2} $, $ m - 1 = {a^2} $,$ sqrt m + sqrt {m - 1} = a + bsqrt 2 $
所以，不存在无解状况。现在问题是怎么求a。如果打表找规律可以知道，n>=2时，a[n]=2*a[n-1]+a[n-2],初始值为a[1]=a[2]=1;
怎么证明呢？网上没看到有证明，所以自己胡扯一下吧。考虑我们已经有了 $ {left( {1{ m{ + }}sqrt 2 } ight)^{n - 2}} = {a_1} + {b_1}sqrt 2 $
那么 $ {left( {1{ m{ + }}sqrt 2 } ight)^{n - 1}} = left( {{a_1} + {b_1}sqrt 2 } ight)left( {1 + sqrt 2 } ight) = {a_2} + {b_2}sqrt 2 $
即 $ {a_2} = {a_1} + 2{b_1},{b_2} = {a_1} + {b_1} $
同理,可以推出 $ {a_3} = {a_2} + 2{b_2} $
带入a1,a2，可以得到 $ {a_3} = 3{a_1} + 4{b_1} = 2{a_1} + {a_2} $
所以满足上面的递推式。
然后矩阵快速幂搞一发就过啦！
51nod1537分解(矩阵快速幂)
分析:先写出前几项,发现都是有解的.记(1+√2)^n=a+b√2,可以归纳证明,当n为奇数时,m=a^2+1,n为偶数时,m=a^2.写出a的递推式,用矩阵快速幂算一下a即可.1#include<iostream>2#include<cstring>3#include<cstdio>4usingnamespacestd;5constintp=1e9+7;6ty 查看详情
51nod-15371537分解(矩阵快速幂+找规律)
题目链接：1537 分解 问(1+sqrt(2)) ^n 能否分解成 sqrt(m) +sqrt(m-1)的形式 如果可以 输出 m%1e9+7 否则 输出noInput一行，一个数n。（n<=10^18）Output一行，如果不存在m输出no，否则输出m%1e9+7In 查看详情
51nod1434区间lcm(质因数分解)
分析:考虑从1到n所有数的质因数分解，记录每个质数的最高次数，同理从n+1循环到2n，如果循环到m时每个质因子的次数都不低于所记录的，则跳出循环，结果即为m。先预处理质数，复杂度为O(nlongn)。1#include<iostream>2#include<... 查看详情
51nod1024矩阵中不重复的元素(质因数分解+map判重）
1024矩阵中不重复的元素题目来源：Project Euler基准时间限制：1秒空间限制：131072KB分值:10难度：2级算法题收藏关注取消关注一个m*n的矩阵。 该矩阵的第一列是a^b,(a+1)^b,.....(a+n-1)^b第二列是a^(b+1),(a+1)^(b+1),.....(a+n-1)^(b+1)......... 查看详情
51nod2122分解质因数(代码片段)
...e/Problem.html#problemId=2122一、题目描述请你帮小瓜将正整数n分解质因数，并从小到大输出所有的质因数（如果一个质因数出现多次，则输出多次）。输入一行一个正整数n，保证1<=n<=10^8。输出若干行，每行表示n的一个质因数。... 查看详情
51nod1061最复杂的数v2
...小于\(x\)的约数个数。反素数有什么性质？把一个反素数分解成\(p_1^a_1p_2^a_2...p_n^a_n\)的形式，则\(a_1\gea_2\ 查看详情
51nod算法马拉松17解题报告
B题（数学题： 问(1+sqrt(2)) ^n 能否分解成 sqrt(m) +sqrt(m-1)的形式 如果可以 输出 m%1e9+7 否则 输出no n<=1e18 刚看题没思路暴力一下吧发现根本没有no的情况那么就好办多了所求的值... 查看详情
bzoj1053&&51nod1060
...：其实就是求1-n之中拥有最多约数的数一个数x的质因数分解为p1^e1*p2^e2*...*pn^en,则正因数的个数为(e1+1)(e2+1)...(en+1)那么发现，正因数的个数和p没有关系那么p越小越好于是，若x是最好的,且x=p1^e1*p2^e2*...*pn^en，则e1<e2<e3<..en，... 查看详情
51nod——t1631小鲨鱼在51nod小学
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1631基准时间限制：1 秒空间限制：131072 KB分值: 20 难度：3级算法题 收藏 关注鲨鱼巨巨2.0（以下简称小鲨鱼）以优异的成绩考入了51nod小学。并依靠算法方面... 查看详情
51nod1185||51nod1072威佐夫博弈
贴个模板：平常的跟高精度java的；int：#pragmacomment(linker,"/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<alg 查看详情
51nod1631小鲨鱼在51nod小学
...题鲨鱼巨巨2.0（以下简称小鲨鱼）以优异的成绩考入了51nod小学。并依靠算法方面的特长，在班里担任了许多职务。 每一个职务都有一个起始时间A和结束时间B，意为小鲨鱼在[A,B]时间内，担任了某职务(inclusively)。 现在... 查看详情
51nod1354：选数字
51nod1354：选数字题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1354题目大意：有$T(Tleqslant20)$组数据，每组给出$n(nleqslant1000)$个数和$K(Kleqslant100,000,000)$，问在这$n$个数中选取若干个，积为$K$的方案数有多少.DP+离散化与... 查看详情
51nod1310：chandrimaandxor
51nod1310：ChandrimaandXOR题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1310题目大意：序列$S={1,2,4,5,...}$，其中任何一个数转为二进制不包括两个连续的$1$。给出一个长度为$N$的正整数数组$A$，$A_1,A_2,...,A_n$记录的是下标... 查看详情
[51nod]配对
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1737求出树的重心，跑spfa#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<string>usingname 查看详情
51nod1232：完美数
51nod1232：完美数题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1232题目大意：如果一个数能够被组成它的各个非$0$数字整除，则称它是完美数。例如：$10$,$11$,$12$,$101$都是完美数，但是$13$就不是完美数（因为$13$不能... 查看详情
51nod2576
题意51nod做法令(f_n,d)为(d)层，目前维宽度为(n)(f_n,d=sumlimits_i=1^nf_i,d-1(n?i+1)^k)构造矩阵转移，上三角对角线相等矩阵，快速算就完了题外话一遍过qwq 查看详情
51nod1728
题意51nod做法要是想不到树就删号重练吧令(F_k)为深度不超过(k)的森林个数的EGF不超过(k)的森林，就是若干棵不超过(k)的树，取掉树的根，就是不超过(k-1)的森林就有(F_k=e^xF_k-1) 查看详情
51nod1773a国的贸易
51nod1773http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1773 #include<cstdio>#include<map>#definegcgetchar()constintmod=1e9+7,inv2=(mod+1)>>1;inta[1<<21],b[ 查看详情