A. Level Statistics

• meaning of the title
  Give you a sequence of game moments, each of which contains p i , c i p_i,c_i pi and ci represent the number of games and customs clearance. You need to judge whether the sequence is reasonable.

• Problem solving ideas
  The parameter of the previous time cannot be smaller than that of the current time, and the increase of customs clearance times is less than that of games.

• AC code

/**
  *@filename:A
  *@author: pursuit
  *@created: 2021-08-13 09:00
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t,n;
int x,y,p,c;
void solve(){
    bool flag = false;
    p = c = 0;
    for(int i = 1; i <= n; ++ i){
        scanf("%d%d", &x, &y);
        if(x < p || y < c || y - c > x - p){
            flag = true;
        }
        p = x, c = y;
    }
    printf("%s\n", flag ? "NO" : "YES");
}
int main(){	
    scanf("%d", &t);
    while(t -- ){
        scanf("%d", &n);
        solve();
    }
    return 0;
}

B. Middle Class

• meaning of the title
  Here you are n n n numbers, you can select some numbers from them and then redistribute them evenly. You need to judge the maximum number ≥ x \geq x ≥x.

• Problem solving ideas
  Naturally, we want to distribute the extra to other numbers, so the choice is less than x x x is also as large as possible. So we can sort these numbers, then take the previous numbers in turn, and know that the average is less than x x x exits, and the previous one is the biggest answer.

• AC code

/**
  *@filename:B
  *@author: pursuit
  *@created: 2021-08-13 09:35
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t,n,x,a[N];
void solve(){
    sort(a + 1, a + n + 1);
    ll sum = 0;
    int cnt = 0;
    for(int i = n; i >= 1; -- i){
        sum += a[i];
        cnt ++;
        if(1.0 * sum / cnt < x){
            cnt --;
            break;
        }
    }
    printf("%d\n", cnt);
}
int main(){	
    scanf("%d", &t);
    while(t -- ){
        scanf("%d%d", &n, &x);
        for(int i = 1; i <= n; ++ i){
            scanf("%d", &a[i]);
        }
        solve();
    }
    return 0;
}

C. Circle of Monsters

• meaning of the title
  have n n Monsters with n rings have health a i a_i ai) and explosion injury b i b_i bi, that is, the second i + 1 i+1 i+1 monster generation b i b_i Shanghai, China. Ask you to kill this n n The minimum cost of n monsters.

• Problem solving ideas
  First of all, we should know that if all monsters are to be killed, there must be a price to pay for killing each monster a i − b i − 1 a_i-b_{i-1} ai − bi − 1, and there must be a monster to start the ring, so we need to pay a direct price a i a_i ai# find the smallest one.

• AC code

/**
  *@filename:C
  *@author: pursuit
  *@created: 2021-08-13 09:42
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 3e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t,n;
ll a[N],b[N],c[N];
void solve(){
    ll sum = 0;
    for(int i = 1; i <= n; ++ i){
        sum += c[i];//Consumption that must be spent.
    }
    ll minn = 1e14;
    for(int i = 1; i <= n; ++ i){
        minn = min(minn,a[i] - c[i]);
    }
    printf("%lld\n", sum + minn);
}
int main(){	
    scanf("%d", &t);
    while(t -- ){
        scanf("%d", &n);
        for(int i = 1; i <= n; ++ i){
            scanf("%lld%lld", &a[i], &b[i]);
            if(i > 1)c[i] = a[i] - b[i - 1] < 0 ? 0 : a[i] - b[i - 1];
        }
        c[1] = a[1] - b[n] < 0 ? 0 : a[1] - b[n];
        solve();
    }
    return 0;
}

D. Minimum Euler Cycle

• meaning of the title
  I'll give you a directed complete graph with n n For n vertices, you need to make each edge go through, find a scheme with the smallest dictionary order, and output it [ l , r ] [l,r] Nodes between [l,r].

• Problem solving ideas
  According to the meaning of the question, we can construct a unique sequence with the smallest dictionary order, such as:
  1   2   1   3   1   4   1 ... 1   n 2   3   2   4 ...   2   n ... 1 1\ 2 \ 1 \ 3 \ 1\ 4 \ 1\dots1 \ n\\2\ 3\ 2 \ 4 \dots \ 2 \ n \\ \dots \\1 1 2 1 3 1 4 1...1 n2 3 2 4... 2 n...1.
  So we can divide it into n n n intervals, of which the first n n The elements of n intervals are 2 × ( n − i ) 2\times (n -i) two × (n − i) Nos. So according to paragraph x x x nodes, we can determine in the second node i i i intervals, and for each interval, where the form is i   i + 1   i   i + 2 ... i \ i +1\ i \ i +2 \dots i ， i+1 ， i ， i+2..., from which we can get.

• AC code

/**
  *@filename:D
  *@author: pursuit
  *@created: 2021-08-13 12:40
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t,n;
ll l,r;
ll pre[N];
int cal(ll x){
    if(x > pre[n - 1])return 1;//Exclude special cases.
    int idx = lower_bound(pre + 1,pre + n + 1,x) - pre;
    //Then pre is idx idx + 1 idx idx + 2 in the interval governed by idx This form.
    x = x - pre[idx - 1];
    return x & 1 ? idx : x / 2 + idx;
}
void solve(){
    for(int i = 1; i <= n; ++ i){
        pre[i] = pre[i - 1] + 2 * (n - i);
    }
    for(ll i = l; i <= r; ++ i){
        printf("%d%c", cal(i), " \n"[i == r]);
    }
}
int main(){	
    scanf("%d", &t);
    while(t -- ){
        scanf("%d%lld%lld", &n, &l, &r);
        solve();
    }
    return 0;
}

E. Divisor Paths

• meaning of the title
  Give you a number D ( < = 1 e 15 ) D(<=1e15) D (< = 1e15), all factors of D (including 1 and itself) form an undirected graph as nodes, for a certain two factors x x x， y y y. If x % y = = 0 x\%y==0 x%y==0 and x / y x/y If x/y is a prime number, then there is a path between X and y with a length of n u m ( x ) − n u m ( y ) num(x)-num(y) num(x) − the edge of num(y), where n u m ( x ) num(x) num(x) stands for x x Number of factors for x. next q ( q ≤ 3 e 5 ) q(q\leq 3e5) q(q ≤ 3e5) times, asking a and b each time, and asking how many shortest paths are between a and b.

• Problem solving ideas
  Not hard to find, a − > b a->b a − > B must pass g c d ( a , b ) gcd(a,b) gcd(a,b) because a , b a,b a. B all divisible g c d ( a , b ) gcd(a,b) gcd(a,b). a a a constantly becoming g c d ( a , b ) gcd(a,b) gcd(a,b) is constantly divided by the quality factor, so we can regard it as a / g c d ( a , b ) = u ( false set up this individual number by u ) a/gcd(a,b)=u (suppose this number is U) a/gcd(a,b)=u (assuming this number is U) becomes 1 1 1, i.e u u The factorial of the sum of the powers of the prime factor of u divided by u u The sum of the factorials of the powers of each prime factor of u. Multiply the two. Note that we need to preprocess factorials and the number of schemes of nodes to improve efficiency.

• AC code

/**
  *@filename:E
  *@author: pursuit
  *@created: 2021-08-13 14:03
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 998244353;
const int INF = 0x3f3f3f3f;

ll d,u,v;
int q,fac[N];
map<ll,ll> p;
void init(){
    //Pretreatment n!
    fac[0] = fac[1] = 1;
    for(int i = 2; i < N; ++ i){
        fac[i] = 1LL * fac[i - 1] * i % P;
    }
}
ll ksm(ll n,ll q){
    ll ans = 1;
    while(q){
        if(q & 1)ans = ans * n % P;
        n = n * n % P;
        q >>= 1;
    }
    return ans;
}
ll cal(ll x){
    //All shortest paths from X to y need to be calculated, and they all pass through gcd(x,y).
    //The shortest path for X to move to gcd(x,y) is the prime factor of X divided by x/(gcd(x,y)), and the order of division is arbitrary.
    ll sum1 = 0,sum2 = 1;
    for(ll i = 2; i * i <= x; ++ i){
        if(x % i == 0){
            ll num = 0;
            while(x % i == 0){
                x /= i;
                num ++;
            }
            sum2 = sum2 * ksm(fac[num], P - 2) % P;//Division takes modular edge multiplication.
            sum1 += num;
        }
    }
    if(x > 1){
        sum1 ++;
    }
    sum1 = sum2 * fac[sum1] % P;
    return sum1;
}
void solve(){
    for(ll i = 1; i * i <= d; ++ i){
        if(d % i == 0){
            p[i] = cal(i);
            p[d / i] = cal(d / i);
        }
    }
    while(q -- ){
        scanf("%lld%lld", &u, &v);
        ll k = __gcd(u,v);
        printf("%lld\n", p[u / k] * p[v / k] % P);
    }
}
int main(){	
    init();
    scanf("%lld%d", &d, &q);
    solve();
    return 0;
}