学步园

#include <cstdio>
#include <cstring>
#define LL __int64
LL a, b, x, y, mod, n;
void gao(LL n, LL &x, LL &y)
{
    if(n == 1)
    {
        x = a % mod, y = b % mod;
        return;
    }
    LL tx, ty;
    gao(n>>1, tx, ty);
    x = (tx * tx - ty * ty) % mod;
    y = 2 * tx * ty % mod;
    if(n & 1)
    {
        LL tt = x;
        x = (a * x - b * y) % mod;
        y = (a * y + b * tt) % mod;
    }
}
int main()
{
    while( ~scanf("%I64d%I64d%I64d%I64d", &a, &b, &n, &mod))
    {
        if(!n)
        {
            printf("1 0\n");
            continue;
        }
        gao(n, x, y);
        if(x < 0) x += mod;
        if(y < 0) y += mod;
        printf("%I64d %I64d\n", x, y);
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#define LL __int64
LL a, b, n, mod;

int main()
{
    int i, j;
    while( ~scanf("%I64d%I64d%I64d%I64d", &a, &b, &n, &mod))
    {
        if(!n)
        {
            printf("1 0\n");
            continue;
        }
        LL x = 1, y = 0, tx = a % mod, ty = b % mod;
        while(n)
        {
            if(n & 1) 
            {
                LL tt = x;
                x = (x * tx - y * ty) % mod;
                y = (tt * ty + y * tx) % mod;
            }
            LL tt = tx;
            tx = (tx * tx - ty * ty) % mod;
            ty = (2 * tt * ty) % mod;
            n >>= 1;
        }
        if(x < 0) x += mod;
        if(y < 0) y += mod;
        printf("%I64d %I64d\n", x, y);
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#define LL __int64
LL a, b, n, mod;
struct complex
{   
    LL a, b;
    complex(){}
    complex(LL a, LL b):a(a%mod),b(b%mod){}
    complex operator *(const complex &p)
    {
        return complex((a*p.a-b*p.b)%mod, (a*p.b+b*p.a)%mod);
    }
};
void gao(LL n, complex &p)
{
    if(n == 1)
    {
        p = complex(a%mod, b%mod);
        return;
    }
    complex q;
    gao(n>>1, q);
    p = q * q;
    if(n & 1)
    {
        complex t = complex(a%mod, b%mod);
        p = p * t;
    }
}
int main()
{
    int i, j;
    while( ~scanf("%I64d%I64d%I64d%I64d", &a, &b, &n, &mod))
    {
        if(!n)
        {
            printf("1 0\n");
            continue;
        }
        complex p;
        gao(n, p);
        if(p.a < 0) p.a += mod;
        if(p.b < 0) p.b += mod;
        printf("%I64d %I64d\n", p.a, p.b);
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#define LL __int64
LL a, b, n, mod;
struct complex
{   
    LL a, b;
    complex(){}
    complex(LL a, LL b):a(a%mod),b(b%mod){}
    complex operator *(const complex &p)
    {
        return complex((a*p.a-b*p.b)%mod, (a*p.b+b*p.a)%mod);
    }
};
void gao(LL n, complex &p)
{
    if(n == 1)
    {
        p = complex(a%mod, b%mod);
        return;
    }
    complex q;
    gao(n>>1, q);
    p = q * q;
    if(n & 1)
    {
        complex t = complex(a%mod, b%mod);
        p = p * t;
    }
}
int main()
{
    int i, j;
    while( ~scanf("%I64d%I64d%I64d%I64d", &a, &b, &n, &mod))
    {
        if(!n)
        {
            printf("1 0\n");
            continue;
        }
        complex p;
        gao(n, p);
        if(p.a < 0) p.a += mod;
        if(p.b < 0) p.b += mod;
        printf("%I64d %I64d\n", p.a, p.b);
    }
    return 0;
}