So Easy!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3432 Accepted Submission(s): 1097
Problem Description A sequence S n is defined as:
Where a, b, n, m are positive integers.┌x┐is the ceil of x. For example, ┌3.14┐=4. You are to calculate S n.
You, a top coder, say: So easy!
Input There are several test cases, each test case in one line contains four positive integers: a, b, n, m. Where 0< a, m < 2 15, (a-1) 2< b < a 2, 0 < b, n < 2 31.The input will finish with the end of file.
Output For each the case, output an integer S n.
Sample Input
2 3 1 2013
2 3 2 2013
2 2 1 2013
Sample Output
4
14
4
思路:
由題意知：（a-1）^2<b<a^2,得到0<|a-sqrt(b)|<1。是以可得f[n]=[(a+sqrt(b))^n]=(a+sqrt(b))^n+ (a-sqrt(b))^n.
由斐波那契通項公式來看，可以設f[n]=p*f[n-1]+q*f[n-2],則可以知道這個遞推式的特征方程為x^2=p*x+q;
特征方程的特征根為a+sqrt(b) 和a-sqrt(b)，那麼可以反推回去得p=2a;q=b-a^2;
即f[n]=2af[n-1]+(b-a^2)*f[n-2],這樣就可以構造矩陣了。
f[n] = (2a b-a^2) * (f[n-1])
f[n-1] (1 0 ) (f[n-2])
進而
f[n] = (2a b-a^2)^(n-2) *(f[2])
f[n-1] (1 0 ) (f[1])
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define N 2
using namespace std;
ll n,m;
struct mat
{
ll m[N][N];
};
mat I=
{
1,0,
0,1
};
mat multi(mat a,mat b)
{
mat c;
int i,j,k;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
c.m[i][j]=0;
for(k=0;k<N;k++)
c.m[i][j]+=a.m[i][k]*b.m[k][j]%m;
c.m[i][j]%=m;
}
}
return c;
}
mat power(mat a,ll k)
{
mat ans=I,p=a;
while(k)
{
if(k&1)
{
ans=multi(ans,p);
k--;
}
k>>=1;
p=multi(p,p);
}
return ans;
}
int main()
{
ll x,y;
mat a;
while(scanf("%lld%lld%lld%lld",&x,&y,&n,&m)!=EOF)
{
a.m[0][0]=2*x%m;a.m[0][1]=((y%m-x*x%m)%m+m)%m;
a.m[1][0]=1;a.m[1][1]=0;
if(n==1)
printf("%lld\n",2*x%m);
else
{
mat ans=power(a,n-2);
ll cnt=(ans.m[0][0]%m*2*(x*x%m+y%m)%m+ans.m[0][1]%m*2*x%m)%m;
cnt%=m;
printf("%lld\n",cnt);
}
}
return 0;
}