主要是利用了斐波那契数列对mod1e9+9时二次剩余的性质。说起来这个性质也是很奇葩，只见过两次应用这个题目的情况，一个是这个题一个是/cf.
二次剩余的定义是 当存在某个x使得x^2 \equiv d(mod p)成立时，称“d是模p的二次剩余”，当对任意不成立时，称“ d是模 p的二次非剩余”
而对于斐波那契数列有更具体的性质：
继续阅读“[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci”
主要是利用了斐波那契数列对mod1e9+9时二次剩余的性质。说起来这个性质也是很奇葩，只见过两次应用这个题目的情况，一个是这个题一个是/cf.
二次剩余的定义是 当存在某个x使得x^2 \equiv d(mod p)成立时，称“d是模p的二次剩余”，当对任意不成立时，称“ d是模 p的二次非剩余”
而对于斐波那契数列有更具体的性质：
继续阅读“[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci”