【51NOD 1195】斐波那契数列的循环节

相关链接

题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1195
二次剩余相关:http://staff.ustc.edu.cn/~lvmin05/jssl/Chap3%20%B6%FE%B4%CE%CA%A3%D3%E0.ppt
二次剩余相关:http://pan.baidu.com/s/1geBDodH
神犇题解:http://blog.csdn.net/acdreamers/article/details/10983813

解题报告

我们分三步走:

  1. 将模数质因数分解
  2. 对于每一个$p_i^m$我们计算其循环节$l_i$
  3. 将所有$l_i$取$lcm$

显然第一步和第三步没有难度
我们考虑第二步,这里有一个神奇得结论:
若$G(p)$为Fibonacci数列在模素数$p$意义下的最短循环节
那么$\bmod p^m$的最短循环节为$G(p)\cdot p^{m-1}$

现在问题转化为求$G(p)$,这里又有一个神奇的结论:
若$5$为$p$的二次剩余,则$G(p)$为$p-1$的因子。否则为$2(p+1)$的因子
然后我们就可以通过从小到大枚举因数+$O(\log n)$判断的方法得到答案了

另外的话,这个算法似乎没有比较准确的复杂度。不过我们可以假装他是$O(\sqrt{n} \log n)$的
再另外的话,这份代码会$T$,但我又不想优化了,反正这个东西也不可能考 QwQ

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

class Fibonacci{
	int ans[4],tra[4],MOD;
	public:
		inline bool cal(int t, int mod) {
			ans[1] = tra[1] = tra[2] = tra[3] = 1;
			ans[0] = ans[2] = ans[3] = tra[0] = 0; MOD = mod;
			Pow(tra, tra, t - 2); Mul(ans, ans, tra);
			return ans[1] == 1 && !ans[0];
		}
	private:
		inline void Pow(int *ans, int *a, int t) {
			static int ret[4],cur[4]; 
			ret[0]=ret[3]=1; ret[1]=ret[2]=0;
			memcpy(cur,a,sizeof(cur));
			for (;t;t>>=1,Mul(cur,cur,cur))
				if (t&1) Mul(ret,cur,ret);
			memcpy(ans, ret, sizeof(ret));
		}
		inline void Mul(int *ans, int *a, int *b) {
			static int ret[4];
			ret[0] = ((ll)a[0] * b[0] + (ll)a[1] * b[2]) % MOD;
			ret[1] = ((ll)a[0] * b[1] + (ll)a[1] * b[3]) % MOD;
			ret[2] = ((ll)a[2] * b[0] + (ll)a[3] * b[2]) % MOD;
			ret[3] = ((ll)a[2] * b[1] + (ll)a[3] * b[3]) % MOD;
			memcpy(ans, ret, sizeof(ret));
		}
}fib;

ll GCD(ll a, ll b) {
	return b? GCD(b, a%b): a;
}

int Pow(int w, int t, int mod) {
	int ret = 1;
	for (;t;t>>=1,w=(ll)w*w%mod)
		if (t&1) ret=(ll)ret*w%mod;
	return ret;
}

inline ll G(ll p) {
	if (p == 2) return 3;
	else if (p == 3) return 8;
	else if (p == 5) return 20;
	static ll LIM = 0; stack<int> stk;
	if (Pow(5, (p-1)/2, p) == 1) LIM = p - 1;
	else LIM = p + 1 << 1; 
	for (int i=1;i*i<=LIM;i++) {
		if (LIM % i == 0) {
			if (fib.cal(i+2, p)) return i;
			else stk.push(LIM / i);
		}
	}
	for (int ret;!stk.empty();) {
		ret = stk.top(); stk.pop();
		if (fib.cal(ret+2, p)) return ret;
	}
}

inline ll cal(int a, int b) {
	static ll INF = 4e18, ret;
	for (ret=G(a);b>1;b--) ret = ret * a;
	return ret;
}

inline ll solve(int mod) {
	static const int N = 1e5;
	static int pri[N],cnt[N],tot;
	if (mod == 1) return 1; tot = 0; 
	for (int i=2;i*i<=mod;i++) {
		if (mod % i == 0) {
			pri[++tot] = i; cnt[tot] = 0;
			for (;mod%i==0;mod/=i) ++cnt[tot];
		}
	} if (mod>1) pri[++tot] = mod, cnt[tot]=1;
	ll ret = 1;
	for (int i=1,tmp;i<=tot;i++) {
		tmp = cal(pri[i], cnt[i]);
		ret = ret / GCD(ret, tmp) * tmp;
	} return ret;
}

int main() {
	for (int T=read();T;T--) 
		printf("%lld\n",solve(read()));
	return 0;
}

【BZOJ 4294】[PA2015] Fibonacci

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4294
神犇题解:http://www.cnblogs.com/clrs97/p/4854720.html

解题报告

做这题,我们需要有一个前置结论:

Fibonacci数列在$\bmod 10^n$的时候,循环节为$6 \times 10^n$

至于这个结论怎么证明,我也不知道
不过这个结论可以用这里的知识自己搞出来:传送门

那么知道了这个结论之后
我们就可以从低位到高位DFS了
每一层只会尝试$0 \sim 9$,虽然看起来会$T$
不过复杂度是玄学,所以跑得飞快

【日常小测】题目1

相关链接

题目传送门:http://paste.ubuntu.com/24087405/
数据生成器:http://paste.ubuntu.com/24087409/
std:http://paste.ubuntu.com/24087412/

题目大意

求$\sum_{i=1}^n{f_i^k}$
其中$f_x$为第$x$项$Fibonacci$数
$n \le 1e18, k \le 1e5$

解题报告

之前鏼爷讲过二次剩余,于是看到这个模数就知道方向了
在暴力求出$\sqrt 5$的二次剩余后,我们可以推出答案长这样
$$\sum_{j=0}^{k}{(-1)^{k-j} \cdot C_k^j \sum_{i-1}^n{(A^jB^{k-j})^i}}$$
于是我们搞一搞组合数,逆元什么的这题就做完啦!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000009;
const int A = 691504013;
const int B = 308495997;
const int REV_SQRT_FIVE = 276601605;
const int N = 100009;

int k,vout,PA[N],PB[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int Pow(int w, LL t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD) 
		if (t & 1) ret = (LL)ret * w % MOD;
	return ret;
}

inline int Mul(int a, LL b) {
	int ret = 0;
	for (;b;b>>=1,(a<<=1)%=MOD)
		if (b & 1) (ret += a) %= MOD;
	return ret;
}

int main() {
	freopen("A.in","r",stdin); 
	freopen("A.out","w",stdout); 
	LL n; cin>>n; k = read();
	PA[0] = PB[0] = 1;
	for (int i=1;i<=k;i++) {
		PA[i] = (LL)PA[i-1] * A % MOD;
		PB[i] = (LL)PB[i-1] * B % MOD;
	}
	for (int i=0,c=1,v;i<=k;i++) {
		v = (LL)PA[i] * PB[k-i] % MOD; 
		if (v == 1) v = Mul(v, n);
		else v = ((LL)Pow(v, n+1) - v) * Pow(v-1, MOD-2) % MOD;
		if (k-i & 1) (vout -= (LL)c * v % MOD) %= MOD;
		else (vout += (LL)c * v % MOD) %= MOD;
		c = ((LL)c * (k - i) % MOD) * Pow(i+1, MOD-2) % MOD; 
	} 
	printf("%d\n",((LL)vout*Pow(REV_SQRT_FIVE,k)%MOD+MOD)%MOD);
	return 0;
}

【BZOJ 4408】[FJOI2016] 神秘数

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4408
神犇题解:http://www.cnblogs.com/ihopenot/p/6179880.html

题解

假如我们给定一个已经排好序的序列{ai}
考虑神秘数产生的原因:\({a_i} > 1 + \sum\limits_{j = 1}^{i – 1} {{a_j}}\)

考虑给定的询问,如果使用函数式线段树进行处理,那么已经排好序了
现在的问题就是如何找到最小的、符合上述要求的\({a_i}\)

这货不满足二分的性质,所以不能用二分
然后我就不会做了 QwQ
这时,神犇ihopenot说:“直接暴力模拟就可以了啊!”
具体来说:

假设当前已经能够凑出1~i中的所有的数
统计1~(i+1)这个区间内所有数的和
如果等于i则停止,否则继续该操作

我们来考虑一下为什么这样做复杂度是正确的:

假设当前能凑出1~i,使用的最大的数为a
那么合法的下一个数一定在a+1到i+1之间
换一句话来说:进行一次增值操作可以“收割”长度为i-a的区间
更进一步:使用的数最小为a+2,能凑出的数至少为i+a+2
更进两步:下一次至少可以收割长度为i的区间
更进三步:每次收割区间的长度会增加ai,而且ai > a(i-1)+1
更进四步:仔细想一想,这货比Fibonacci数列增长还要快,所以至多进行log(n)次

然后这题就用函数式线段树来暴力迭代就可以辣!
这™是我第四次被Fibonacci数列坑了 QwQ
ps:这货貌似是双倍经验,参见BZOJ_4299

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100000+9;
const int M = 3300000;
const int INF = 1e9;
 
int n,m,arr[N];
 
inline int read(){
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
 
namespace Chair_Tree{
    #define CT Chair_Tree
    int ch[M][2],sum[M],root[N];
    int ans_tmp,cnt;
     
    void insert(int p, int &w, int l, int r, int v) {
        w = ++cnt; sum[w] = sum[p] + v;
        memcpy(ch[w],ch[p],sizeof(ch[w]));
        if (l < r) {
            int mid = l + r + 1 >> 1;
            if (v < mid) insert(ch[p][0], ch[w][0], l, mid-1, v);
            else insert(ch[p][1],ch[w][1], mid, r, v);
        }   
    }
     
    inline void insert(int p, int v) {
        insert(root[p-1],root[p],1,INF,v);
    }
     
    void query(int p, int w, int l, int r, int v) {
        if (l == r) {
            ans_tmp += sum[w] - sum[p];
        } else {
            int mid = l + r + 1 >> 1;
            if (v < mid) query(ch[p][0],ch[w][0],l,mid-1,v);
            else {
                ans_tmp += sum[ch[w][0]] - sum[ch[p][0]];
                query(ch[p][1],ch[w][1],mid,r,v);
            }
        }
    }
     
    inline int query(int l, int r, int v) {
        ans_tmp = 0;
        query(root[l-1],root[r],1,INF,v);
        return ans_tmp;
    }
};
 
int main(){
    n = read();
    for (int i=1;i<=n;i++) { 
        arr[i] = read();
        CT::insert(i,arr[i]);
    }
         
    m = read();
    for (int j=1,l,r,cur,tmp;j<=m;j++) {
        l = read(); r = read(); cur = 0;
        while ((tmp = CT::query(l,r,cur+1)) > cur) {
            cur = tmp;
        }
        printf("%d\n",cur+1);
    }
    return 0;
}