Given the value ofa+bandabyou will have to find the value ofan+bn
Input
The input file contains several lines of inputs. Each line except the last line contains3non-negative integersp,qandn. Herepdenotes the value ofa+bandqdenotes the value ofab. Input is terminated by a line containing only two zeroes. This line should not be processed. Each number in the input file fits in a signed32-bit integer. There will be no such input so that you have to find the value of00.
Output
For each line of input except the last one produce one line of output. This line contains the value ofan+bn.You can always assume thatan+bnfits in a signed 64-bit integer.
Sample InputOutput for Sample Input
10 16 2 7 12 3 0 0
68
91
Problem setter: Shahriar Manzoor, Member of Elite Problemsetters’ Panel
Special Thanks: Mohammad Sajjad Hossain
题意很明显就是求a^n+b^n；
我们发现f0=2,f1=a+b,f2=a^2+b^2=(a+b)*f1-a*b*f2….
依次递推，令p=a+b,q=a*b;
所以fi=fi-1*p-fi-2*q;
构造出矩阵后就可以求解了。
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<bitset>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef long long LL;typedef pair<int,int>pil;const int INF = 0x3f3f3f3f;struct Matrix{LL mat[2][2];void Clear(){CLEAR(mat,0);}};Matrix mult(Matrix m1,Matrix m2){Matrix ans;for(int i=0;i<2;i++)for(int j=0;j<2;j++){ans.mat[i][j]=0;for(int k=0;k<2;k++)ans.mat[i][j]=ans.mat[i][j]+m1.mat[i][k]*m2.mat[k][j];}return ans;}Matrix Pow(Matrix m1,LL b){Matrix ans;ans.Clear();for(int i=0;i<2;i++)ans.mat[i][i]=1;while(b){if(b&1)ans=mult(ans,m1);b>>=1;m1=mult(m1,m1);}return ans;}LL p,q,n;int main(){while(scanf("%lld%lld%lld",&p,&q,&n)==3){Matrix A;if(n==0){puts("2");continue;}if(n==1){printf("%lld\n",p);continue;}A.mat[0][0]=p;A.mat[0][1]=-q;A.mat[1][0]=1;A.mat[1][1]=0;A=Pow(A,n-1);LL ans=A.mat[0][0]*p+A.mat[0][1]*2;printf("%lld\n",ans);}return 0;}HDU 4565So Easy!
Problem Description
A sequence Snis 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 Sn. 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 < 215, (a-1)2< b < a2, 0 < b, n < 231.The input will finish with the end of file.
Output
For each the case, output an integer Sn.
Sample Input
2 3 1 20132 3 2 20132 2 1 2013
Sample Output
4144
题目要求这个式子答案，，我们发现(a-1)^2<b<a^2这就意味着a-1<sqrt(b)<a;
所以又(a+sqrt(b))^n+(a-sqrt(b))^n为整数，所以式子答案即为(a+sqrt(b))^n+(a-sqrt(b))^n
简化下，就是上面的a’=a+sqrt(b),b’=a-sqrt(b);所以p=2*a,q=a*a-b;
问题转化为上题做法。
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<bitset>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef long long LL;typedef pair<int,int>pil;const int INF = 0x3f3f3f3f;struct Matrix{LL mat[2][2];void Clear(){CLEAR(mat,0);}};LL a,b,n,m;Matrix mult(Matrix m1,Matrix m2){Matrix ans;for(int i=0;i<2;i++)for(int j=0;j<2;j++){ans.mat[i][j]=0;for(int k=0;k<2;k++)ans.mat[i][j]=(ans.mat[i][j]+m1.mat[i][k]*m2.mat[k][j])%m;}return ans;}Matrix Pow(Matrix m1,LL b){Matrix ans;ans.Clear();for(int i=0;i<2;i++)ans.mat[i][i]=1;while(b){if(b&1)ans=mult(ans,m1);b>>=1;m1=mult(m1,m1);}return ans;}int main(){while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&m)!=EOF){LL p=2*a,q=a*a-b;//x^n+y^nMatrix A;if(n==1){printf("%I64d\n",p);continue;}A.mat[0][0]=p;A.mat[0][1]=-q;A.mat[1][0]=1;A.mat[1][1]=0;A=Pow(A,n-1);LL ans=A.mat[0][0]*p%m;ans=((ans+A.mat[0][1]*2)%m+m)%m;printf("%I64d\n",ans);}return 0;}
当你能爱的时候就不要放弃爱
