时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
You are given four positive integers x0,x1,a,bx0,x1,a,b. And you know for all i≥2.
Given two positive integers n, and MOD, please calculate xnx_nxn modulo MOD.
Does the problem look simple? Surprise! The value of n may have many many digits!
Given two positive integers n, and MOD, please calculate xnx_nxn modulo MOD.
Does the problem look simple? Surprise! The value of n may have many many digits!
输入描述
The input contains two lines.
The first line contains four integers x0,x1,a,b(1≤x0,x1,a,b≤10^9).
The second line contains two integers n, MOD (1≤n<10(10^6),10^9<MOD≤2×10^9, n has no leading zero).
输出描述
Print one integer representing the answer.
输入
1 1 1 1 10 1000000001
输出
89
说明
The resulting sequence x is Fibonacci sequence. The 11-th item is 89.
输入
1315 521 20185 5452831 9999999999999999999999999999999999999 1000000007
输出
914730061
题意:已知x0,x1,a,b,n,mod,和公式,求对mod取余。
题解:十进制快速幂。
代码:
#include<bits/stdc++.h>
using namespace std;
long long x0,x1,a,b,mod;
struct node
{
long long Martix[2][2];
node operator *(const node&n) const
{
node sum;
int i,j,k;
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
sum.Martix[i][j]=0;
for(k=0;k<2;k++)
sum.Martix[i][j]=(sum.Martix[i][j]+Martix[i][k]*n.Martix[k][j])%mod;
}
return sum;
}
};
node ans,t;
char n[1000005];
node quick(node A,int k);
int main()
{
int i,k,l;
scanf("%lld%lld%lld%lld",&x0,&x1,&a,&b);
scanf("%s%lld",n, &mod);
ans.Martix[0][0]=ans.Martix[1][1]=1;
ans.Martix[1][0]=ans.Martix[0][1]=0;
t.Martix[0][0]=a;t.Martix[0][1]=b;
t.Martix[1][0]=1;t.Martix[1][1]=0;
l=strlen(n);
for(i=l-1;i>=0;i--)
{
ans=ans*quick(t,n[i]-'0');
t=quick(t,10);
}
printf("%lld",(x1*ans.Martix[1][0]+x0*ans.Martix[1][1])%mod);
system("pause");
return 0;
}
node quick(node A,int k)
{
node sum;
sum.Martix[0][0]=sum.Martix[1][1]=1;
sum.Martix[0][1]=sum.Martix[1][0]=0;
while(k)
{
if(k&1) sum=sum*A;
k>>=1;
A=A*A;
}
return sum;
}