• 最近变忙了，可能之后写的题解会更加精简了，尽量还是还原题意和思路吧

A： DZY Loves Fibonacci Numbers | CF 446C

题意

• DZY Loves Fibonacci Numbers | CF 446C
  $F_i$ 表示第 $i$ 个斐波那契数
  长度为 $n$ 的序列 $a_n$
  （1）区间加斐波那契数：$[l,r]$，让区间中的数 $a_i$ 增加 $F_{i-l+1}$
  （2）查询区间和，取模
• 区间长河查询次数 $3e5$

思路

• 区间加斐波那契数和之前的区间加等差非常像，都是要打标记，然后标记下传。
  注意，一个等差数列加一个等差数列仍然为一个等差数列
  一个类斐波那契加一个类斐波那契仍然为一个类斐波那契
  类斐波那契数列就是：
  $$\begin{gathered} G_1=a,G_2=b \\ {G}_n=G_{n-1}+G_{n-2}=a{F}_{n-2}+b{F}_{n-1} \end{gathered}$$
• 还要算一个区间和，斐波那契的前缀和我们有公式：
  $$\sum _{i=1}^n{F}_i=F_{n+2}-F_2$$
• 然后重要的一点，任意的一个类斐波那契数列，我只要知道 $G_1,G_2$ 就可以表示整个独特的数列了。所以我们只存这两个头即可。

代码

• 时间复杂度：$O(n\log n)$

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}const int MAX = 3e5+50;
const int MOD = 1e9+9;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-7;#define ls (p<<1)
#define rs (p<<1|1)
#define md ((l+r)>>1)ll fib[MAX];void get_Fibs(int n){fib[1] = fib[2] = 1;for(int i = 3;i <= n;++i)fib[i] = (fib[i-1] + fib[i-2]) % MOD;
}ll get_Fib(int x,ll a,ll b){		// 求 G_X ,其中 G_1=a,G_2=b// if(x == 0)show("ERROR");if(x == 1)return a;if(x == 2)return b;return (a * fib[x-2] % MOD + b * fib[x-1] % MOD) % MOD;
}ll get_FibSum(int n,ll a,ll b){		// 求 G_1 + ... + G_n ,其中 G_1=a,G_2=breturn (get_Fib(n + 2,a,b) - get_Fib(2,a,b) + MOD) % MOD;
}int aa[MAX];
ll tree[MAX*4];
ll A[MAX*4],B[MAX*4];
inline void push_up(int p){tree[p]=(tree[ls]+tree[rs]) % MOD;
}
inline void build(int p,int l,int r){A[p] = B[p] = 0;if(l == r){tree[p] = aa[l];return;}build(ls,l,md);build(rs,md+1,r);push_up(p);
}
inline void add(int p,int l,int r,ll a,ll b){		// 下传，只是修改类斐波那契数列的前两个值即可A[p] = (A[p] + a) % MOD;B[p] = (B[p] + b) % MOD;tree[p] = (tree[p] + get_FibSum(r-l+1,a,b)) % MOD;
//    show(l,r,a,b,get_FibSum(r-l+1,a,b));
}
inline void push_down(int p,int l,int r){if(A[p]){
//        show(l,r,A[p],B[p]);add(ls,l,md,A[p],B[p]);add(rs,md+1,r,get_Fib(md-l+2,A[p],B[p]),get_Fib(md-l+3,A[p],B[p]));A[p] = 0;B[p] = 0;}
}
inline void update(int p,int l,int r,int ux,int uy,int lef){if(ux <= l && uy >= r){
//        show(l,r,get_Fib(l - lef + 1,1,1),get_Fib(l - lef + 2,1,1));add(p,l,r,get_Fib(l - lef + 1,1,1),get_Fib(l - lef + 2,1,1));return;}push_down(p,l,r);if(ux <= md)update(ls,l,md,ux,uy,lef);if(uy >  md)update(rs,md+1,r,ux,uy,lef);push_up(p);
}
inline ll query(int p,int l,int r,int qx,int qy){ll res = 0;if(qx <= l && r <= qy)return tree[p];push_down(p,l,r);if(qx <= md)res = (res + query(ls,l,md,qx,qy)) % MOD;if(qy >  md)res = (res + query(rs,md+1,r,qx,qy)) % MOD;return res;
}int main()
{get_Fibs(300005);
//    for(int i = 1;i <= 10;++i){
//        show(i,get_Fib(i,1,5));
//        show(i,get_FibSum(i,1,1));
//    }int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= n;++i)scanf("%d",&aa[i]);build(1,1,n);for(int i = 1;i <= m;++i){int op,l,r;scanf("%d%d%d",&op,&l,&r);if(op == 1)update(1,1,n,l,r,l);else printf("%lld\n",query(1,1,n,l,r));}return 0;
}

B：GCD Counting | CF 990G

题意

• GCD Counting | CF 990G
  给定一颗树。树上的一条简单路径的权值记为这个路径上所有点的权值的 $\gcd$
  求对于每一个整数 $i=1\sim 2e5$，有多少条路径的权值为 $i$
• 点数，点权 $\le 2e5$

思路

• 求路径方案数，直接点分治。
  但是询问特别多，但是考虑到 $\le 2e5$ 的数的最多因子个数只有 $180$，所以我们暴力 $for$ 小桶 + 大桶，时间复杂度不会很坏。

代码

• 时间复杂度：$O(n\log n\times 180^2)$，但是达不到这么多.
  $1300/4500Ms$

#include<bits/stdc++.h>
using namespace std;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}
typedef long long ll;
const int MAX = 2e5+50;
const int MOD = 1e9+7;vector<int>V[MAX];
int sum,root;
int sz[MAX],ff[MAX];
bool vis[MAX];
map<int,ll>big,sml;
int val[MAX];
ll ans[MAX];
void get_root(int x,int f){sz[x] = 1;ff[x] = 0;for(auto it : V[x]){int y = it;if(y == f || vis[y])continue;get_root(y,x);sz[x] += sz[y];ff[x] = max(ff[x],sz[y]);}ff[x] = max(ff[x],sum-sz[x]);if(ff[x] < ff[root])root=x;
}
void get_gcd(int x,int f,int gcd){sml[gcd]++;ans[gcd]++;for(auto it : V[x]){int y = it;if(y == f || vis[y])continue;get_gcd(y,x,__gcd(gcd,val[it]));}
}
void cal(int x){
//    show(x);big.clear();ans[val[x]]++;for(auto it : V[x]){int y = it;if(vis[y])continue;sml.clear();get_gcd(y,x,__gcd(val[x],val[y]));for(auto it : sml){for(auto it2 : big){ans[__gcd(it.first,it2.first)] += it.second * it2.second;}}for(auto it : sml){big[it.first] += it.second;}}
}
void solve(int x){vis[x] = 1;cal(x);for(auto it : V[x]){int y = it;if(vis[y])continue;root = 0;sum = sz[y];get_root(y,y);solve(root);}
}int main()
{int n;scanf("%d",&n);for(int i = 1;i <= n;++i)scanf("%d",&val[i]);for(int i = 1;i < n;++i){int ta,tb;scanf("%d%d",&ta,&tb);V[ta].push_back(tb);V[tb].push_back(ta);}ff[0] = n;sum  = n;root = 0;get_root(1,0);solve(root);for(int i = 1;i <= 200000;++i)if(ans[i])printf("%d %lld\n",i,ans[i]);return 0;
}

C：Relatively Prime Powers | CF 1036F

题意

• Relatively Prime Powers | CF 1036F
  $1e5$ 组询问，每次问 $2\sim x$ 中有多少个数字是优雅的。
• 一个数字是优雅的，当这个数字被写成 $num=2^{k_1}{3}^{k_2}{5}^{k_3}\cdots$
  写成质数的乘积形式时，$\gcd (k_1,k_2,\cdots )=1$
• $x\le 10^{18}$

思路

• 首先，题目非常妙。一个数不是优雅的，也就是这个 $\gcd =k$
  此时这个数字一定可以被写成 $num=i^k$
  问题就变成成 $2\sim x$ 中有多少个数能被表示成 $i^k$，其中 $k\ge 2$
• 考虑到求什么的 $\gcd =k$ 很难求时，我们考虑莫比乌斯反演。
  设 $f(k)$ 表示 $\gcd =k$
  设 $F(k)$ 表示 $\gcd |k$
  首先我们有 $f(k)={\sum }_{k|d}\mu (d)F(\frac{d}{k})$
  因为我们只用求 $f(1)=\sum \mu (d)F(d)$
• 然后，$F(d)=\lfloor x^{1/d}\rfloor -1$ ，注意精度问题即可。

代码

• 时间复杂度：$O(T\times 60^2)$

#include<bits/stdc++.h>
using namespace std;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}
typedef long long ll;
const int MAX = 2e5+50;
const int MOD = 1e9+7;ll qpow(ll a,ll n){/* */ll res = 1LL;while(n){if(n&1)res=res*a%MOD;a=a*a%MOD;n>>=1;}return res;}
ll qpow(ll a,ll n,ll p){a%=p;ll res = 1LL;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
long double npow(long double a,ll n){/* */long double res = 1.0;while(n){if(n&1)res=res*a;a=a*a;n>>=1;if(res<0||a<0)return 0;}return res;}
ll inv(ll a){/* */return qpow(a,MOD-2);}
ll inv(ll a,ll p){return qpow(a,p-2,p);}int mu[100];int get_Mu(int x){if(x == 1)return 1;int cnt = 0;for(int i = 2;i * i <= x;++i){if(x % i == 0){x /= i;cnt++;if(x % i == 0)return 0;}}if(x > 1)cnt++;if(cnt&1)return -1;return 1;
}int main()
{for(int i = 1;i <= 60;++i){mu[i] = get_Mu(i);}ll T;scanf("%lld",&T);while(T--){ll n;scanf("%lld",&n);ll ans = 0;for(int i = 1;i <= 60;++i){ll tmp = (ll)pow(n,1.0L / i) + 2;while(npow(tmp,i) > n)--tmp;		// 可能有精度偏差ans += (tmp - 1) * mu[i];}printf("%lld\n",ans);}return 0;
}

D：Alice, Bob, Oranges and Apples | CF 585C

题意

• Alice, Bob, Oranges and Apples | CF 585C
  开始 $A$ 有一个橘子，$B$ 有一个苹果。
  每一轮，要么是 $A$ 把他等数量的苹果和橘子从商店里给 $B$
  要么是 $B$ 把他等数量的苹果和橘子从商店里给 $A$
  最后他们总共有 $x$ 个橘子，$y$ 个苹果。
  求输出一种给的方案，或者判断是非法解。
• $1\le x,y\le 10^{18},xy>1$

思路

• 里面牵扯到 $Stern-BrocotTree$ 的东西
  这个 $SBT$ 里面，分子和分母必须是互质的，否则是无解的。
  然后你发现，如果 $A$ 给 $B$ 四次，逆过程，相当于 $B$ 拿掉了四次 $A$ 的水果。
  最后终点是一个橙子和一个苹果。考虑怎么从 $(1,1)$ 走到 $(x,y)$ 其实就是考虑逆过程，怎么从 $(x,y)$ 走到 $(1,1)$
• 然后怎么搞方案呢？
  假设

表	橙子	苹果
A	a	c
B	b	d

• 然后 $A$ 给 $B$ 了 $k$ 次，就变成：

表	橙子	苹果
A	a	c
B	b+ak	d+ck

• 然后我们发现
  第一次总的橙子数为 $a+b$，苹果数为 $c+d$
  之后，总的橙子数为 $a+b+ak$，总的苹果数为 $c+d+ck$
  貌似没有什么规律
• 但是换一个角度思考
  第一次 $A$ 的水果数为 $a+c$，$B$ 的水果数为 $b+d$
  之后， $A$ 的水果数为 $a+c$，$B$ 的水果数为 $b+d+k(a+c)$
  这个总的水果数像欧几里得辗转相加减一样！
  所以最终的做法也就是类似这样，每次水果数多的人放回自己的水果，直到最后变成开始的时候。

代码

• 时间复杂度：$O(\log xy)$

#include<bits/stdc++.h>
using namespace std;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}
typedef long long ll;
const int MAX = 1e6+50;
const int MOD = 1e9+7;int main()
{ll x,y;cin >> x >> y;if(__gcd(x,y) > 1){puts("Impossible");return 0;}while(min(x,y) > 1){if(x > y)printf("%lldA",x/y),x %= y;else printf("%lldB",y/x),y%=x;}if(x > 1)printf("%lldA",x-1);else printf("%lldB",y-1);return 0;
}
/***/