LightOJ 1070-Algebrail Problem行列の高速べき乗

タイトル:http://lightoj.com/volume_showproblem.php?problem=1070
1070-Algebrail Proble m

PDF(English)
Statistics
Forum
Time Limit: 2 second(s)
メモリLimit: 32 MB
Given the value of a+b and ab. you will have to find the value of an+bn. a. and b not necessarly have to be real numbers.
Input
Input starts with an integer T(≦10000)、denoting the number of test cases.
Each case contains three non-negative integers、 p,q and n.Here p denotes the value of a+b and q denotes the value of ab.Each number in the input file fits in a signed 32-bit integer.The e will beのsuch input so that you have to find the value of 00.
Output
For each test case,print the case number and (an+bn) modulo 264.
Sample Input
Output for Sample Input
2 10 16 2 7 12 3
Case 1:68 Case 2:91
 
件名:
p=a+bをあげます.q=ab
算出(a^n+b^)mod 2^64
作り方:
mod 2^64はunsigned longを開くので、lluでいいです.上限に達すると自動的に型を取ります.
そして公式です.私は公式を推す中で見つけた法則です.
a^2+b^2=(a+b)*(a+b)-2*a*b
a^3+b^3=(a^2+b^2)*(a+b)-a*b(a+b)
a^4+b^4=(a^3+b^3)*(a+b)-a*b(a^2+b^2)
G(n)=a^n+b^nを設定する
G(n)=G(n-1)*p-G(G-2)*q
そして速いべき乗です.

#include<stdio.h>
#include<string.h>
#define Matr 5 //    ,            1       Matr  +1       100
#define ll unsigned long long
struct mat//     ，a    ，size      1      size    
{
    ll a[Matr][Matr];
    mat()//    
    {
        memset(a,0,sizeof(a));
    }
};
int Size=  2; 

mat multi(mat m1,mat m2)//         ，      ， 0         
{
    mat ans=mat(); 
    for(int i=1;i<=Size;i++)
        for(int j=1;j<=Size;j++)
            if(m1.a[i][j])//       
                for(int k=1;k<=Size;k++)
                    ans.a[i][k]=(ans.a[i][k]+m1.a[i][j]*m2.a[j][k]); //i k  j 
    return ans;
}

mat quickmulti(mat m,ll n)//      
{
    mat ans=mat();
    int i;
    for(i=1;i<=Size;i++)ans.a[i][i]=1;
    while(n)
    {
        if(n&1)ans=multi(m,ans);//          .
        m=multi(m,m);
        n>>=1;
    }
    return ans;
}

void print(mat m)//      ，debug    
{  
    int i,j;  
    printf("%d
",Size);  
    for(i=1;i<=Size;i++)  
    {  
        for(j=1;j<=Size;j++)
			printf("%llu ",m.a[i][j]);  
        printf("
");  
    }  
}  
int main()
{  
	/*
	ll a,b;
	while(scanf("%llu",&a)!=EOF)
		printf("%llu
",-a+18446744073709551615+1);
	*/
	int t;
	int cas=1;
	scanf("%d",&t);
	while(t--)
	{
		ll p,q,n;
		int p1,q1;
		scanf("%lld%lld%llu",&p,&q,&n);// p a+b q ab 



		ll tem=18446744073709551615-q+1;

		mat gouzao=mat(),chu=mat();//             
		chu.a[1][1]=p;
		chu.a[1][2]=p*p+2*tem;
		chu.a[1][3]=q;
		printf("Case %d: ",cas++);
		if(n==0)
			printf("2
");
		else if(n==1)
			printf("%llu
",p);
		else if(n==2)
			printf("%llu
",p*p+2*tem);
		else
		{ 
			gouzao.a[1][1]=0;
			gouzao.a[2][1]=1;
			gouzao.a[1][2]=tem;
			gouzao.a[2][2]=p;  
			//print(gouzao);
			printf("%llu
",multi(chu,quickmulti(gouzao,n-2)).a[1][2]); 
		} 
	} 
	return 0;
}

/*
ans^=n -
mat ans=mat();
ans.size=Size;
   ans  
ans=quickmulti(ans,n,mod);

void print(mat m)//      ，debug  
{
    int i,j;
    printf(%dn,m.size);
    for(i=1;i=m.size;i++)
    {
        for(j=1;j=m.size;j++)printf(%d ,m.a[i][j]);
        printf(n);
    }
}
*/