无理数取模（二次剩余）

如果有理数 $a^k\equiv b(modp)$，那么$a\equiv \sqrt[k]{b}(modp)$。
例如：$383008016^2\equiv 616991993^2\equiv 5(mod10^9+9)$，那么$383008016\equiv 616991993\equiv \sqrt{5}(mod10^9+9)$。

验证一个无理数在模数 $p$ 下是否有其对应的有理数，可以通过打表获取。

# include <stdio.h> 

typedef long long ll;

const int p = 1e9 + 9;

int main() {
   
	for (ll i = 1; i <= p; i++) {
   
		if (i * i % p == 5) {
   
			printf("%d\n", i);
		}
	}	
	
	return 0;
}

运行结果：

此方法的时间复杂度为O(n)，对于更低复杂度的算法，请参考洛谷中https://www.luogu.com.cn/problem/P5491的题解

斐波那契数列的通项公式
$$F_n=\frac{(\frac{1+\sqrt{5}}{2}{)}^n-(\frac{1-\sqrt{5}}{2}{)}^n}{\sqrt{5}}$$
如果求 $F_n\%(10^9+9)$的结果，可以令$A$ = $\frac{1+\sqrt{5}}{2}$， $B$ = $\frac{1-\sqrt{5}}{2}$, $C$ = $\frac{1}{\sqrt{5}}$。
根据费马小定理，当模数为质数时，$A$ = $(1+383008016)\ast pow(2,mod-2)\%mod$， $B$ = $(1-383008016+mod)\ast pow(2,mod-2)\%mod$， $C$ = $pow(383008016,mod-2)\%mod$。

# include <stdio.h> 

typedef long long ll;

const int sq5 = 383008016;
const int mod = 1e9 + 9;

int qpow(int x, int p) {
   
	int ans = 1 % mod;
	while (p) {
   
		if (p & 1) {
   
			ans = 1ll * ans * x % mod;
		}
		x = 1ll * x * x % mod;
		p >>= 1;
	}
	
	return ans;
}

int main() {
   
	int A = 1ll * (1 + sq5) * qpow(2, mod - 2) % mod;
	int B = 1ll * (1 - sq5 + mod) * qpow(2, mod - 2) % mod;
	int C = qpow(sq5, mod - 2);
	printf("%d\n%d\n%d", A, B, C);
	
	return 0;
}

运行结果：

那么当 $mod=10^9+9$ 时， $F_n\%(mod)$ = $C\ast (A^n-B^n+mod)\%mod$

# include <stdio.h>

typedef long long ll;

const int mod = 1e9 + 9;

const int A = 691504013;	// (1 + sqrt(5) / 2
const int B = 308495997;	// (1 - sqrt(5) / 2
const int C = 276601605;	// 1 / sqrt(5)

ll qpow(ll x, ll p) {
   
	ll ans = 1 % mod;

	while (p) {
   
		if (p & 1) {
   
			ans = ans * x % mod;
		}
		x = x * x % mod;
		p >>= 1;
	}

	return ans;
}

int main() {
   
	int T;
	scanf("%d", &T);
	while (T--) {
   
		ll n;
		scanf("%lld", &n);
		ll re1 = qpow(A, n);
		ll re2 = qpow(B, n);
		ll ans = (re1 - re2 + mod) % mod * C % mod;
		printf("%lld\n", ans);
	}

	return 0;
}

测试OJ: https://witacm.com/problem.php?pid=1512
当然，此题也可以通过矩阵快速幂来求。

# include <iostream>

typedef long long ll;

const int mod = 1e9 + 9;
struct  Node {
   
	ll m[2][2];
	Node operator * (Node b) {
   
		Node x;
		x.m[0][0] = (( this->m[0][0] * b.m[0][0] ) % mod + ( this->m[0][1] * b.m[1][0] ) % mod) % mod;
		x.m[0][1] = (( this->m[0][0] * b.m[0][1] ) % mod + ( this->m[0][1] * b.m[1][1] ) % mod) % mod;
		x.m[1][0] = (( this->m[1][0] * b.m[0][0] ) % mod + ( this->m[1][1] * b.m[1][0] ) % mod) % mod;
		x.m[1][1] = (( this->m[1][0] * b.m[0][1] ) % mod + ( this->m[1][1] * b.m[1][1] ) % mod) % mod;

		return x;
	}
};

const Node I = {
   1, 0, 0, 1};
const Node T = {
   1, 1, 1, 0};

Node qpow(Node x, ll p) {
   
	Node ans = I;

	while (p) {
   
		if (p & 1) {
   
			ans = ans * x;
		}
		x = x * x;
		p >>= 1 ;
	}

	return ans;
}

ll fib(ll num) {
   
	if (num == 0 || num == 1) {
   
		return num;
	}

	if (num == 2) {
   
		return 1;
	}

	Node ans = qpow(T, num);
	return ans.m[0][1];
}

int main() {
   
	int T;
	scanf("%d", &T);
	while (T--) {
   
		ll n;
		scanf("%lld", &n);

		printf("%lld\n", fib(n));
	}

	return 0;
}