• Complement field, collect 2000+ questions of some missing math theories submitted in high numbers.

A: SUM and REPLACE | CF 920F

meaning of the title

• SUM and REPLACE | CF 920F
  Given length is n n Sequence of n a n a_n an​
  Yes m m m operations for the following:

1. R E P L A C E   l ,   r REPLACE\ l,\ r REPLACE   l,   r, for each i ∈ [ l , r ] i\in[l,r] i < [l,r], let a i = D ( a i ) a_i=D(a_i) AI = D(ai), where D ( x ) D(x) D(x) representation x x Number of factors for x
2. S U M   l   r SUM\ l\ r SUM   l   r, find out ∑ i = l r a i \sum_{i=l}^r a_i ∑i=lr​ai​

• 1 ≤ n , m ≤ 3 ⋅ 1 0 5 1\le n,m\le 3\cdot 10^5 1≤n,m≤3⋅105
  1 ≤ a i ≤ 1 0 6 1\le a_i\le 10^6 1≤ai​≤106

thinking

• Simple questions. Not many operations per number can become 1 1 1 or 2 2 2, and then it doesn't change.
  Write an extra marker to make sure that the intervals covered do not change.

Code

• Time Complexity: O ( n log ⁡ n ) O(n\log n) O(nlogn)

#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...);}
#define ls (p<<1)
#define rs (p<<1|1)
#define md ((l+r)>>1)
#define ll long long
const int MAX = 1e6+50;
ll aa[MAX];
ll tree[MAX*4];
bool fin[MAX*4];

int mp[MAX];
int tau[MAX];

int cnt;
bool vis[MAX];
int pri[MAX];

void shai(int n){
    tau[1] = 1;mp[1] = 0;
    for(int i = 2;i <= n;++i){
        if(!vis[i]){
            pri[++cnt] = i;
            tau[i] = 2;mp[i] = 1;
        }
        for(int j = 1;j <= cnt && i * pri[j] <= n;++j){
            vis[i * pri[j]] = 1;
            if(i % pri[j]){
                tau[i * pri[j]] = tau[i] * 2;
                mp[i * pri[j]] = 1;
            }else{
                tau[i * pri[j]] = tau[i] / (mp[i] + 1) * (mp[i] + 2);
                mp[i * pri[j]] = mp[i] + 1;
                break;
            }
        }
    }
}

inline void push_up(int p){
    tree[p]=tree[ls]+tree[rs];
    fin[p] = fin[ls] & fin[rs];
}
inline void build(int p,int l,int r){
    fin[p] = 0;
    if(l == r){
        tree[p] = aa[l];
        if(tree[p] == tau[tree[p]])fin[p] = 1;
        return;
    }
    build(ls,l,md);
    build(rs,md+1,r);
    push_up(p);
}
inline void update(int p,int l,int r,int ux,int uy){
    if(fin[p])return;
    if(l == r){
        tree[p] = tau[tree[p]];
        if(tree[p] == tau[tree[p]])fin[p] = 1;
        return;
    }
    if(ux <= md)update(ls,l,md,ux,uy);
    if(uy >  md)update(rs,md+1,r,ux,uy);
    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];
    if(qx <= md)res += query(ls,l,md,qx,qy);
    if(qy >  md)res += query(rs,md+1,r,qx,qy);
    return res;
}
int main()
{
    shai(1000000);
    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){
        ll op,t1,t2;
        scanf("%lld",&op);
        if(op == 1){
            scanf("%lld%lld",&t1,&t2);
            update(1,1,n,t1,t2);
        }else{
            scanf("%lld%lld",&t1,&t2);
            printf("%lld\n",query(1,1,n,t1,t2));
        }
    }
    return 0;
}

B: Roman and Numbers | CF 401D

meaning of the title

• Roman and Numbers | CF 401D
  Given a number x x x, arrange all its digits to get a new number without leading zeros y y y
  satisfy y ∣ m y|m y_m, so different y y Number of y
• 1 ≤ n < 1 0 18 1\le n< 10^{18} 1≤n<1018
  1 ≤ m ≤ 100 1\le m\le 100 1≤m≤100

thinking

• We can use the shape pressure to record which numbers we have selected so far.
  Then, consider the final integer division m m m, let's record one more state to indicate that the currently selected component is numeric modulus m m What is m.
  Just remember d p [ S ] [ j ] dp[S][j] dp[S][j] indicates that the selected set of numbers is S S S, and the values of this number are modeled m m m is j j Number of schemes for j.
• Then each time we pick a new number, we simply recurse down. The final answer is d p [ a l l ] [ 0 ] dp[all][0] dp[all][0]

Code

• Time Complexity: O ( 2 18 × 18 × 100 ) O(2^{18}\times 18 \times 100) O(218×18×100)

#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 = 1e5+50;
const int MOD = 1e9+7;

int cnt;
int arr[20];
int num[20];
ll dp[1<<18][105];

ll getFac(int x){
    ll res = 1;
    for(ll i = 2;i <= x;++i)res *= i;
    return res;
}

int main()
{
    ll n;int m;cin >> n >> m;
    while(n){
        arr[cnt++] = n % 10;
        num[n %10]++;
        n /= 10;
    }
    int ed = 1<<cnt;
    dp[0][0] = 1;

    for(int i = 0;i < ed;++i){
        for(int j = 0;j < m;++j){
            if(!dp[i][j])continue;
            for(int k = 0;k < cnt;++k){
                if(i>>k&1)continue;
                if(i == 0 && arr[k] == 0)continue;
                dp[i|(1<<k)][(j*10+arr[k])%m] += dp[i][j];
            }
        }
    }

//    show(dp[ed-1][0]);

    for(int i = 0;i < 10;++i)dp[ed-1][0] /= getFac(num[i]);

    cout << dp[ed-1][0];


    return 0;
}

C: Cut | CF 1516D

meaning of the title

• Cut | CF 1516D
  Give you a length of n n Sequence of n a n a_n an, for you m m m Queries
  Give you one each time you ask l , r l,r l,r, ask you this paragraph a l ∼ a r a_l\sim a_r al ar is divided into at least a few consecutive subsegments to satisfy each subsegment's l c m lcm lcm equals the product of each element in this subparagraph?
• 1 ≤ n , q , a i ≤ 1 0 5 1\le n,q,a_i\le 10^5 1≤n,q,ai​≤105

thinking

• good topic \color{blue}{good topic} A good topic
  What if it's just a question?
  This subparagraph of the first topic must satisfy that elements in an interval are not mutually prime.
  Every time from the far left x x x Start, be greedy, get the largest y y y, satisfied ( a x , a x + 1 , ⋯   , a y ) (a_x,a_x+1,\cdots,a_y) Elements in (ax, ax +1,..., ay) are not interdependent. Then start the next interval.
• There are many branches of thought here. We propose and solve one by one.
  (1) What inspiration does this greed have?
  Consider each of our elements a i a_i If ai is the left vertex of a subsegment, the subscript of the rightmost vertex of that subsegment is recorded as n x t [ i ] nxt[i] nxt[i]
  As the left vertex moves to the right, the noninterprime condition becomes easier and easier, so our subscript to the right vertex is monotonic.
  That is, we can use something like a double pointer to get everything n x t [ i ] nxt[i] nxt[i]
  (2) How to judge that elements in a subparagraph are not mutually prime to get our n x t [ i ] nxt[i] nxt[i] ？
  If we get every element a i a_i Set of all prime factors of ai A \mathbb{A} A, let's start with one for each prime factor v i s [ p ] vis[p] vis[p] indicates whether this prime factor already exists in this subsegment. If one of my new numbers is added p p PSatisfaction was added before v i s [ p ] = 1 vis[p]=1 vis[p]=1, of course, that doesn't satisfy the reciprocity condition. New Add Number and Delete Number Pair v i s [ p ] vis[p] The impact of vis[p] is well written.
  Notice that the number of factors for a number is O ( n 1 / 3 ) O(n^{1/3}) O(n1/3) level. But let's not go directly O ( n 3 / 2 ) O(n^{3/2}) O(n3/2) to get all the factors, we can enumerate the factors before enumerating the numbers, so the complexity becomes O ( n log ⁡ n ) O(n\log n) O(nlogn)
  (3) With n x t [ i ] nxt[i] nxt[i] array, how do we get an answer to a question?
  I jump every time n x t [ i ] nxt[i] nxt[i] until n x t [ i ] ≥ r nxt[i]\ge r If nxt[i]is greater than or equal to r, then of course the number of jumps is the smallest number of subsections in this interval.
  (4) But it is not very good to ask many times? How to optimize?
  Consider jumping once a time n x t [ i ] nxt[i] nxt[i], really bad. We can use a multiplication table to skip more than one at a time so that the number of skips can be controlled in log ⁡ \log log times. Note that we need to make a change n x t [ i ] nxt[i] Change the definition of the nxt[i] array to the next position of the rightmost right vertex. This allows you to use the multiplication table directly.
  Multiplication table n x t [ i ] [ j ] nxt[i][j] nxt[i][j] means from i i i Start, jump 2 j 2^j Step 2j, where is the next position in the right interval. If it ≤ r \le r Less than or equal to r means we want to jump. Of course, here's the j j j is enumerated from large to small.

Code

• Time Complexity: O ( ( n + q ) log ⁡ n ) O((n+q)\log n) O((n+q)logn)

#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 = 1e5+50;
const int MOD = 1e9+7;

int cnt;
bool vis[MAX];
int pri[MAX];

vector<int>fac[MAX];

int aa[MAX];
int nxt[MAX][30];

int vis2[MAX];

void shai(int x){
    for(int i = 2;i <= x;++i){
        if(!vis[i])pri[++cnt]=i;
        for(int j = 1;j <= cnt && i * pri[j] <= x;++j){
            vis[i * pri[j]] = 1;
            if(i % pri[j] == 0)break;
        }
    }

    for(int i = 1;i <= cnt;++i)
    for(int j = 1;j * pri[i] <= x;++j){
        fac[pri[i] * j].push_back(i);
    }
}

void change(int x,int k){
    int val = aa[x];
    for(auto it : fac[val])vis2[it] += k;
}


bool check(int nxtPos){
    int val = aa[nxtPos];
    for(auto it : fac[val])if(vis2[it])return false;
    return true;
}

int main()
{
    shai(100000);
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i = 1;i <= n;++i){
        scanf("%d",&aa[i]);
    }
    int nxtPos=0;
    for(int i = 1;i <= n;++i){
        while(nxtPos+1 <= n && check(nxtPos+1)){
            change(nxtPos+1,1);
            nxtPos++;
        }
        change(i,-1);
        nxt[i][0] = nxtPos+1;
//        show(i,nxtPos);
    }

    for(int j = 0;j <= 20;++j)
        nxt[n+1][j] = n+1;

    for(int j = 1;j <= 20;++j)
    for(int i = 1;i <= n;++i)
        nxt[i][j] = nxt[nxt[i][j-1]][j-1];

    while(q--){
        int l,r;scanf("%d%d",&l,&r);
        int cnt = 0;
        int now = l;
        for(int i = 20;~i;--i){
            if(nxt[now][i] <= r){
                cnt += (1<<i);
                now = nxt[now][i];
            }
        }
        printf("%d\n",cnt+1);
    }

    return 0;
}

D: Recovering BST | CF 1025D

meaning of the title

• Recovering BST | CF 1025D
  Given the middle traversal order of a tree a n a_n an​
  Ask if you can build one like this B S T BST BST tree that satisfies two connected nodes gcd ⁡ > 1 \gcd >1 gcd>1
• 2 ≤ n ≤ 700 2\le n\le 700 2≤n≤700
  2 ≤ a i ≤ 1 0 9 2\le a_i\le 10^9 2≤ai​≤109

thinking

• Come up and we'll definitely wonder if we can define it d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k] represents an interval [ i , j ] [i,j] [i,j] Build a tree B S T BST BST, where the root is k k k.
  Then consider the transfer. We enumerate i , j , k i,j,k i,j,k, as long as you find a root on the left and a root on the right, satisfy d p [ i ] [ k − 1 ] [ r 1 ] = d p [ k + 1 ] [ r ] [ r 2 ] = 1 dp[i][k-1][r1]=dp[k+1][r][r2]=1 dp[i][k_1][r1]=dp[k+1][r][r2]=1, then two roots and a k a_k ak's gcd ⁡ > 1 \gcd >1 Gcd>1, you can transfer it.
  But the time complexity of doing this is O ( n 4 ) O(n^4) O(n4), timed out.
• Then I go and fool around with greedy constructs, but obviously it's not going to work, I have to do it anyway d p dp dp. We have to consider optimization.
  The problem is that the transition is too complex and the state is complex, although it seems necessary.
  Notice some necessary properties. If we could build one [ l , r ] [l,r] The tree of [l,r], whatever its root is, its father is either a l − 1 a_{l-1} al_1, or a r + 1 a_{r+1} ar+1, or it has no father.
• So, we define the state d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1] dp[i][j][0/1] indicates whether a tree can be built [ i , j ] [i,j] The tree of [i,j], and the root's father is a i a_{i} ai (or root's father is) a r a_{r} ar). Notice the range here!
  Consider transfer. d p [ i ′ ] [ j ′ ] [ 0 / 1 ] = d p [ i ] [ k ] [ 1 ] & d p [ k ] [ j ] [ 0 ] dp[i^\prime][j^\prime][0/1]=dp[i][k][1]\&dp[k][j][0] Dp[i'][j'][0/1]=dp[i][k][1]&dp[k][j][0], and gcd ⁡ ( k , f a ) > 1 \gcd(k,fa)>1 gcd(k,fa)>1.
  Obviously, we'll set the root as k k k, pull out the left subtree to satisfy the right father k k k, the right subtree satisfies the left father k k k.
  Then look at Yes 0 / 1 0/1 0/1 Decision f a fa fa is i − 1 i-1 i_1 or j + 1 j+1 j+1, then transfer.
  Last if it exists d p [ 1 ] [ n ] [ 0 / 1 ] = 1 dp[1][n][0/1]=1 dp[1][n][0/1]=1 That's reconfigurable, otherwise it won't work
• Note that we can Preprocess in advance g g [ i ] [ j ] = gcd ⁡ ( a i , a j ) gg[i][j]=\gcd(a_i,a_j) gg[i][j]=gcd(ai, aj), or another log ⁡ \log log

Code

• Time Complexity: O ( n 3 ) O(n^3) O(n3), but there is a lot of redundancy, so it won't run full.

#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 = 1e5+50;
const int MOD = 1e9+7;

int aa[705];
int gg[705][705];
bool dp[705][705][2];

int main()
{
    int n;cin >> n;
    for(int i = 1;i <= n;++i)cin >> aa[i],dp[i][i][0] = dp[i][i][1] = 1;

    for(int i = 0;i <= n + 1;++i)
    for(int j = 0;j <= n + 1;++j)
        gg[i][j] = __gcd(aa[i],aa[j]);


    for(int Len = 1;Len <= n;++Len)
    for(int L = 1;L + Len - 1 <= n;++L){
        int R = L + Len - 1;
//        show(L,R,dp[L][R][0],dp[L][R][1]);
        for(int k = L;k <= R;++k){
            if(dp[L][k][1] && dp[k][R][0]){
                if(gg[L-1][k] > 1)dp[L-1][R][0] = 1;
                if(gg[R+1][k] > 1)dp[L][R+1][1] = 1;
                if(L == 1 && R == n){
                    puts("Yes");
                    return 0;
                }
            }
        }
    }
    puts("No");
    return 0;
}
/**
4
23 247 299 703
*/

E: Array and Operations | CF 498C

meaning of the title

• Array and Operations | CF 498C
  Given a sequence a n a_n an​
  given m m m opposite edge ( i m , j m ) (i_m,j_m) (im, jm), where satisfies i k + j k i_k+j_k ik+jk is odd and i k < j k i_k<j_k ik​<jk​
  You can choose a pair of edges at a time ( x , y ) (x,y) (x,y), and then select one v v v, satisfy v > 1 v>1 V>1 and v ∣ a x v|a_{x} v_ax and v ∣ a y v|a_y v∣ay​
  Then you succeed in one operation and let a x = a x / v a_x=a_x/v ax​=ax​/v， a y = a y / v a_y=a_y/v ay​=ay​/v
  Ask you how many times you can do it
• 2 ≤ n ≤ 100 2\le n\le 100 2≤n≤100
  1 ≤ m ≤ 100 1\le m\le 100 1≤m≤100
  1 ≤ a i ≤ 1 0 9 1\le a_i\le 10^9 1≤ai​≤109

thinking

• Very few numbers and edges. We directly consider taking out each prime factor, and then for all edges, we connect the same mass factor of these two elements to each other, and the capacity is positive and infinite.
  Because each mass factor can only be calculated once, we split the point, the entry point connects the exit point, and the capacity is 1 1 1
  Run one maximum stream at the end.

Code

• Time Complexity: O ( can with too ) O (OK) O (OK)

#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;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

struct edge{
    int to;
    ll cap;
    int rev;
};
vector<edge>G[MAX];
int level[MAX];     ///Depth Array
int iter[MAX];      ///Current Arc Optimization

void add_edge(int from,int to,ll cap){
    G[from].push_back({to,cap,G[to].size()});
    G[to].push_back({from,0,G[from].size()-1});
}
void bfs(int s){
    memset(level,-1,sizeof(level));
    level[s] = 0;
    queue<int>Q;
    Q.push(s);
    while(!Q.empty()){
        int v = Q.front();Q.pop();
        for(auto it : G[v]){
            if(it.cap > 0 && level[it.to] < 0){
                level[it.to] = level[v] + 1;
                Q.push(it.to);
            }
        }
    }
}
ll dfs(int v,int t,ll f){
    if(v == t)return f;
    for(int &i = iter[v];i < G[v].size();++i){
        edge &e = G[v][i];
        if(e.cap > 0 && level[v] < level[e.to]){
            ll d = dfs(e.to,t,min(f,e.cap));
            if(d > 0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}
ll max_flow(int s,int t){
    ll flow = 0;
    while(1){
        bfs(s);
        if(level[t] < 0)return flow;
        memset(iter,0,sizeof(iter));
        ll f = -1;
        while(f){
            f = dfs(s,t,LINF);
            flow += f;
        }
    }
}

int aa[MAX];

vector<pair<int,int> >V[MAX];

int main()
{
    int n,m;cin >> n >> m;
    for(int i = 1;i <= n;++i)cin >> aa[i];

    int cnt = 0;
    for(int i = 1;i <= n;++i){
        int tmp = aa[i];
        for(int j = 2;j * j <= tmp;++j){
            if(tmp % j == 0){
                while(tmp % j == 0){
                    tmp /= j;
                    V[i].push_back(make_pair(++cnt,j));
                }
            }
        }
        if(tmp > 1)V[i].push_back(make_pair(++cnt,tmp));
    }

    int S = 0,T = 2 * cnt + 1;

    for(int i = 1;i <= n;++i){
        for(auto it : V[i]){
            int x = it.first;
            add_edge(x,x+cnt,1);
            if(i&1)add_edge(S,x,INF);
            else add_edge(x+cnt,T,INF);
        }
    }

    while(m--){
        int ta,tb;
        cin >> ta >> tb;
        for(auto it : V[ta])
        for(auto it2: V[tb]){
            if(it.second == it2.second){
                if(ta&1)add_edge(it.first+cnt,it2.first,INF);
                else add_edge(it2.first+cnt,it.first,INF);
            }
        }
    }

    cout << max_flow(S,T);
    return 0;
}
/**

*/

F: Send Boxes to Alice (Hard Version) | CF 1254B2

meaning of the title

• Send Boxes to Alice (Hard Version) | CF 1254B2
  Given a sequence a n a_n an​
  Each time you move, you can select two adjacent elements (that is, two adjacent elements) a b s ( p 1 − p 2 ) = 1 abs(p1-p2)=1 abs(p1_p2)=1), and then put the element in one of the locations + 1 +1 +1, element at another location − 1 -1 −1
  Ask you the minimum number of moves to satisfy this sequence gcd ⁡ > 1 \gcd>1 gcd>1
  If not, output − 1 -1 −1
  Data satisfies at least one positive integer a i a_i ai​
• 1 ≤ n ≤ 1 0 6 1\le n\le 10^6 1≤n≤106
  0 ≤ a i ≤ 1 0 6 0\le a_i\le 10^6 0≤ai​≤106

thinking

• good topic \color{blue}{good topic} A good topic
  When you see this question, think about it for each gcd ⁡ = k \gcd=k gcd=k, I will go c h e c k check check and calculate the minimum number of moves.
  But with each operation, it's not good to have one plus one and one minus one.
  Then let's think a different way. We remember the prefix and S i = a 1 + a 2 + ⋯ + a i S_i=a_1+a_2+\cdots+a_i Si​=a1​+a2​+⋯+ai​
  Easy to get, we want to make S i ∣ k S_i|k Si k, and each move we make only one S i S_i Si adds one or subtracts one.
  That's great.
• For each specific k k k， S i S_i The operations to be subtracted or added by Si satisfy the following: k k The multiple of k, which is what we take min ⁡ { S i % k , k − S i % k } \min\{S_i\%k,k-S_i\%k\} min{Si​%k,k−Si​%k}
• But for each k k k It's not very good that we all ask for it once. At this point we thought, our k k k Just take a reasonable prime number. Because above % k \%k With the precondition of%k and the segment is a multiple, the smaller the segment length, the greater the flexibility.

Code

• Time Complexity: O ( n 3 / 2 ) O(n^{3/2}) O(n3/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 = 1e6+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int aa[MAX];
ll pre[MAX];


ll check(ll x,int n){
    ll ans = 0;
    for(int i = 1;i <= n;++i){
        ans += min(pre[i]%x,x-(pre[i]%x));
    }
//    show(x,ans);
    return ans;
}

int main()
{
    ll sum = 0;
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;++i)scanf("%d",&aa[i]),sum += aa[i],pre[i] = pre[i-1] + aa[i];

    ll ans = LINF;

    for(ll i = 2;i * i <= sum;++i){
        if(sum % i == 0){
            ans = min(ans,check(i,n));
            while(sum % i == 0)sum /= i;
        }
    }
    if(sum > 1)ans = min(ans,check(sum,n));

    if(ans == LINF)puts("-1");
    else printf("%lld",ans);

    return 0;
}