2016年10月25日数学考试：斐波那契数列与矩阵快速幂的应用

1. 我们先来看看几个有关斐波那契数列的引理。
Gcd(F[n+1],F[n])=1;
F[m+n]=F[m-1]F[n]+F[m]F[n+1];
Gcd(F[n+m],F[n])=Gcd(F[n],F[m]);
由以上三个引理有：Gcd(F[n],F[m])=F[Gcd(n,m)];

#include 
#include 
#include 

const int mod = 19491001;
int n;
int tx, ty;

struct data {
    long long x1, x2, x3, x4;
    data (long long x1 = 1, long long x2 = 0, long long x3 = 0, long long x4 = 1) : x1(x1), x2(x2), x3(x3), x4(x4) {};
};

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

data operator * (data a, data b) {
    data c;
    c.x1 = (a.x1 * b.x1 + a.x2 * b.x3) % mod;
    c.x2 = (a.x1 * b.x2 + a.x2 * b.x4) % mod;
    c.x3 = (a.x3 * b.x1 + a.x4 * b.x3) % mod;
    c.x4 = (a.x3 * b.x2 + a.x4 * b.x4) % mod;
    return (c);
}

data qpow(data x, int v) {
    data ans;
    while (v > 0) {
        if (v & 1) ans = ans * x;
        x = x * x;
        v >>= 1;
    }
    return (ans);
}

int main () {
    freopen("fibonacci.in", "r", stdin);
    freopen("fibonacci.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &tx, &ty);
        int ans = gcd(tx, ty);
        data cur(0, 1, 1, 1);
        cur = qpow(cur, ans - 2);
        long long tans = ((cur.x2 + cur.x4) % mod + mod) % mod;
        printf("%I64d\n", tans);
    }
    return 0;
}

#include 
#include 
#include 

unsigned long long f[100];
unsigned long long n;

int main () {
    freopen("gold.in", "r", stdin);
    freopen("gold.out", "w", stdout);
    f[1] = 1;
    f[2] = 1;
    for (int i = 3; i <= 93; i++) f[i] = f[i-1] + f[i-2];
    f[94] = 0 - 1;
    //for (int i = 1; i <= 94; i++) printf("%I64u\n", f[i]);
    scanf("%I64u", &n);
    for (int i = 2; i <= 93; i++) {
        if (f[i] <= n && f[i+1] > n) {
            printf("%I64u/%I64u\n", f[i-1], f[i]);
        }
    }
    return 0;
}