1537 分解
基準時間限制：0.5 秒 空間限制：131072 KB 分值: 80
難度：5級算法題
收藏
關注
問(1+sqrt(2)) ^n 能否分解成 sqrt(m) +sqrt(m-1)的形式
如果可以 輸出 m%1e9+7 否則 輸出no
Input
一行，一個數n。（n<=10^18）
Output
一行，如果不存在m輸出no，否則輸出m%1e9+7
Input示例
2
Output示例
9
可以構造出：
假設（1-sqrt（2））N-1次為：A+B*sqrt2
則（1-sqrt（2））N次為：A+2*B +（A+B）*sqrt2
類斐波那契---
矩陣| 1 2|
|1 1 |
最後結果為sqrt（m）+sqrt（m-1）
要對m取模---
是以--A+B*sqrt2===sqrt（A*A）+sqrt(2*B*B)
當某一步為（A+10^9+7）+B*sqrt2時---
下一步為（A+10^9+7+2*B）+（B+A+10^9+7）*sqrt2--
等價于取模後---A+B*sqrt2----的
下一步為：（A+2*B）+（B+A）*sqrt2
即對A和B取模不會影響最後的結果。
代碼：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
LL mod=1000000007;
struct node{
LL shu[2][2];
void clear()
{
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
shu[i][j]=0;
}
node operator * (const node &B) const{
node C;
C.clear();
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
for (int k=0;k<2;k++)
C.shu[i][j]=(C.shu[i][j]+shu[i][k]*B.shu[k][j])%mod;
return C;
}
}A,B;
int main()
{
LL n;
scanf("%lld",&n);
if (n==0)
{
printf("1\n");
return 0;
}
LL nn=n;
A.clear();
for (int i=0;i<2;i++)
A.shu[i][i]=1;
for (int i=0;i<2;i++)
B.shu[i][i]=1;
B.shu[0][1]=2;B.shu[1][0]=1;
nn--;
while (nn)
{
if (nn&1)
A=A*B;
B=B*B;
nn/=2;
}
LL a=(A.shu[0][0]+A.shu[0][1])%mod;
LL b=(A.shu[1][0]+A.shu[1][1])%mod;
if (n%2==0)
{
a=(a*a)%mod;
printf("%lld\n",a);
}
else
{
b=(b*b*2)%mod;
printf("%lld\n",b);
}
return 0;
}