- I've been busy recently. Maybe the solution to the problem will be more concise. Try to restore the meaning and ideas of the problem
A: DZY Loves Fibonacci Numbers | CF 446C
meaning of the title
- DZY Loves Fibonacci Numbers | CF 446C
F i F_i Fi ， indicates the second i i i Fibonacci numbers
Count Reg n n Sequence of n a n a_n an
(1) Interval Gabonese number: [ l , r ] [l,r] [l,r], let the number in the interval a i a_i ai} increase F i − l + 1 F_{i-l+1} Fi−l+1
(2) Query interval sum, modulo - Interval long river query times 3 e 5 3e5 3e5
thinking
- Interval plus Fibonacci numbers are very similar to the previous interval plus arithmetic difference. They are marked and then passed down.
Note that an arithmetic sequence plus an arithmetic sequence is still an arithmetic sequence
One Fibonacci plus one Fibonacci is still a Fibonacci
The Fibonacci like sequence is:
G 1 = a , G 2 = b G n = G n − 1 + G n − 2 = a F n − 2 + b F n − 1 G_1=a,G_2=b\\ G_n=G_{n-1}+G_{n-2}=aF_{n-2}+bF_{n-1} G1=a,G2=bGn=Gn−1+Gn−2=aFn−2+bFn−1 - We also need to calculate an interval sum, the prefix of Fibonacci and we have the formula:
∑ i = 1 n F i = F n + 2 − F 2 \sum_{i=1}^n F_i=F_{n+2}-F_2 i=1∑nFi=Fn+2−F2 - Then the important thing is, any Fibonacci like sequence, I just need to know G 1 , G 2 G_1,G_2 G1, G2 ， can represent the whole unique sequence. So we only save these two heads.
code
- Time complexity: O ( n log n ) O(n\log n) O(nlogn)
#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){ // Find G_X, where 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){ // Find G_1 + ... + G_n, where G_1=a,G_2=b
return (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){ // Pass it down, just modify the first two values of Fibonacci series
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
meaning of the title
- GCD Counting | CF 990G
Given a tree. The weight of a simple path in the tree is recorded as the weight of all points on the path gcd \gcd gcd
For each integer i = 1 ∼ 2 e 5 i=1\sim 2e5 i=1 ∼ 2e5, how many paths have the weight of i i i - Point weight ≤ 2 e 5 \le 2e5 ≤2e5
thinking
- Find the number of path schemes and divide and conquer directly.
But there are a lot of inquiries, but considering ≤ 2 e 5 \le 2e5 The maximum number of factors ≤ 2e5 is only 180 180 180, so we are violent f o r for for small bucket + large bucket, the time complexity will not be very bad.
code
- Time complexity:
O
(
n
log
n
×
18
0
2
)
O(n\log n \times 180^2)
O(nlogn × 1802), but not so much
1300 / 4500 M s 1300/4500Ms 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
meaning of the title
- Relatively Prime Powers | CF 1036F
1 e 5 1e5 1e5 group questioning, each time 2 ∼ x 2\sim x How many numbers in 2 ∼ x are elegant. - A number is elegant when it is written as
n
u
m
=
2
k
1
3
k
2
5
k
3
⋯
num=2^{k_1}3^{k_2}5^{k_3}\cdots
num=2k13k25k3⋯
When written as the product of prime numbers, gcd ( k 1 , k 2 , ⋯ ) = 1 \gcd(k_1,k_2,\cdots)=1 gcd(k1,k2,⋯)=1 - x ≤ 1 0 18 x\le 10^{18} x≤1018
thinking
- First of all, the topic is very wonderful. A number is not elegant, that's it
gcd
=
k
\gcd=k
gcd=k
This number must be written as n u m = i k num=i^k num=ik
The problem becomes 2 ∼ x 2\sim x How many numbers in 2 ∼ x can be expressed as i k i^k ik, where k ≥ 2 k\ge 2 k≥2 - Considering what to ask for
gcd
=
k
\gcd=k
When gcd=k is difficult to find, we consider Mobius inversion.
set up f ( k ) f(k) f(k) indicates gcd = k \gcd=k gcd=k
set up F ( k ) F(k) F(k) indicates gcd ∣ k \gcd|k gcd∣k
First of all, we have f ( k ) = ∑ k ∣ d μ ( d ) F ( d k ) f(k)=\sum_{k|d}\mu(d)F(\frac{d}{k}) f(k)=∑k∣dμ(d)F(kd)
Because we just ask f ( 1 ) = ∑ μ ( d ) F ( d ) f(1)=\sum\mu(d)F(d) f(1)=∑μ(d)F(d) - then, F ( d ) = ⌊ x 1 / d ⌋ − 1 F(d)=\lfloor x^{1/d}\rfloor-1 F(d) = ⌊ x1/d ⌋ − 1, just pay attention to the accuracy.
code
- Time complexity: O ( T × 6 0 2 ) O(T\times 60^2) O(T×602)
#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; // There may be accuracy deviation
ans += (tmp - 1) * mu[i];
}
printf("%lld\n",ans);
}
return 0;
}
D: Alice, Bob, Oranges and Apples | CF 585C
meaning of the title
- Alice, Bob, Oranges and Apples | CF 585C
start A A A there is an orange, B B B there is an apple.
Every round, or A A A take his waiting quantity of apples and oranges from the store B B B
Or B B B take his waiting quantity of apples and oranges from the store A A A
In the end, they had a total of x x x oranges, y y y apples.
Output a given solution, or judge whether it is an illegal solution. - 1 ≤ x , y ≤ 1 0 18 , x y > 1 1\le x,y\le 10^{18},xy>1 1≤x,y≤1018,xy>1
thinking
- It involves
S
t
e
r
n
−
B
r
o
c
o
t
T
r
e
e
Stern-Brocot\ Tree
Stern−Brocot Tree stuff
this S B T SBT In SBT, the numerator and denominator must be coprime, otherwise there is no solution.
Then you find that if A A A give B B B four times, inverse process, equivalent to B B B took it off four times A A A's fruit.
The final destination is an orange and an apple. Consider how to start from ( 1 , 1 ) (1,1) (1,1) go to ( x , y ) (x,y) (x,y) is actually considering the inverse process ( x , y ) (x,y) (x,y) go to ( 1 , 1 ) (1,1) (1,1) - Then what's the plan?
hypothesis
| surface | orange | Apple |
|---|---|---|
| A | a | c |
| B | b | d |
- then A A A give B B B k k k times, it becomes:
| surface | orange | Apple |
|---|---|---|
| A | a | c |
| B | b+ak | d+ck |
- Then we found out
The total number of oranges for the first time is a + b a+b a+b, the number of apples is c + d c+d c+d
After that, the total number of oranges is a + b + a k a+b+ak a+b+ak, the total number of apples is c + d + c k c+d+ck c+d+ck
There seems to be no law - But think about it another way
for the first time A A The number of fruits in A is a + c a+c a+c， B B The number of fruits in B is b + d b+d b+d
After that, A A The number of fruits in A is a + c a+c a+c， B B The number of fruits in B is b + d + k ( a + c ) b+d+k(a+c) b+d+k(a+c)
The total number of fruits is like Euclid's tossing and subtracting!
So the final approach is similar. People who have a large number of fruits each time put back their fruits until it finally becomes the beginning.
code
- Time complexity: O ( log x y ) O(\log xy) O(logxy)
#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;
}
/**
*/