hdu 3221 오라정리 + 빠른 멱 + 매트릭스 빠른 멱

우선 이 문제는 귀속 호출된 계수 문제이다
최종 반환은 각각 1시 a회와 2시 b회로 계수 원리에 따라 이루어진다.
귀속의 호출 메커니즘과 배열 조합의 곱셈 원칙에 따라 f[n]=f[n-1]*f[n-2]를 얻어낸다.
반면에 점차적인 성장은 지수가 증가함에 따라 f[n-1]*f[n-2]는 동일한 지수 형식으로 전환할 수 있고 지수의 생각가로 전환할 수 있으며 피보나치 수열의 성질을 연상할 수 있다.
동적 기획의 사상을 이용하여 행렬의 빠른 멱과 빠른 멱을 통해 최적화한다.
그 다음은 동여의 문제로 지수가 매우 큰 상황에서 오라의 정리를 이용하여 하락할 수 있다.
A^x  = A^(x%phi+phi)mod p
동여정리를 응용하면 이 문제는 쉽게 해결될 것이다.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

struct mat 
{
    LL m[3][3];
    mat ( )
    {
        memset ( m , 0 ,sizeof(m));
    }
};

mat multi ( mat a , mat b , LL mod  )
{
    mat c;
    for ( LL i = 1 ; i < 3 ; i++ )
        for ( LL j = 1 ; j < 3 ; j++ )
            if ( a.m[i][j] )
                for ( LL k = 1 ; k < 3 ; k++ )
                    c.m[i][k] = ( c.m[i][k] + a.m[i][j]*b.m[j][k] )%mod;
    return c;
}

mat quickmulti ( mat a , LL n , LL mod )
{
    mat ans;
    for ( LL i = 1 ; i < 3 ; i++ ) ans.m[i][i] = 1;
    while ( n )
    {
        if ( n&1 ) ans = multi ( ans , a, mod );
        a = multi ( a , a , mod );
        n >>= 1;
    }
    return ans;
}

LL pow ( LL num , LL n , LL mod )
{
    LL ans = 1;
    while ( n )
    {
        if ( n&1 ) ans = ( ans * num )%mod;
        num = (num*num)%mod;
        n>>=1;
    }
    return ans;
}

LL euler ( LL x )
{
    LL res = x;
    for ( int i = 2 ; i*i <= x ; i++ )
    {
        if ( x%i ) continue;
        res -= res/i;
        while ( x%i == 0 ) x /= i; 
    }
    if ( x > 1 ) res -= res/x;
    return res;
}

LL index ( LL n , LL phi )
{
    int a = 1 , b = 0 , temp , i ;
    for ( i = 1 ; i <= n ; i++ )
    {
        temp = a + b;
        b = a;
        a = temp;
        if ( temp >= phi ) break;
    }
    if ( i > n )
       return a; 
    mat ma,mb;
    ma.m[1][1] = mb.m[1][1] = mb.m[1][2] = mb.m[2][1] = 1;
    mb = quickmulti ( mb , n , phi );
    ma = multi ( ma , mb , phi );
    return ma.m[1][1]%phi + phi;
}

int t ;
LL a , b , p , n;

int main ( )
{
    scanf ( "%d" , &t );
    int c = 0;
    while ( t-- )
    {
        c++;
        scanf ( "%lld%lld%lld%lld" , &a , &b , &p , &n );
        printf ( "Case #%d: ",c );
        if ( a == 0 || b == 0 )
        {
            printf ( "0
");
            continue;
        }
        if ( n == 1 )
        {
            printf ( "%I64d
" , a%p );
            continue;
        }
        if ( n == 2 )
        {
            printf ( "%I64d
" , b%p );
            continue;
        }
        if ( p == 1 )
        {
            printf ("0
");
            continue;
        }
        LL phi = euler ( p );
        LL fb = index (n-2,phi) , fa = index ( n-3,phi );
        LL ans = pow ( b , fb , p )* pow ( a , fa , p ) %p ;
        printf ( "%I64d
" , ans );
     }
}