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

### 解题报告

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

### 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

### 解题报告

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

## 【日常小测】题目1

### 题目大意

$n \le 1e18, k \le 1e5$

### 解题报告

$$\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] 神秘数

### 题解

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;
}