D:

/*CodeForces 920D - Tanks [ DP ]核心思想是判断是否能用 a[i]%k 来构成 V%kDP并记录路径即可，剩下的就是加K减K操作*/#include 
     
      using namespace std;#define LL long longconst int N = 5005;int n, k ,v;LL a[N];int b[N], d[N][N], pre[N][N];bool used[N];struct Ans {    int cnt, x, y;};vector
      
        ans;bool solve() {    for (int i = 1; i <= n; i++)        if (v == a[i]) return 1;    if (v == 0) {        ans.push_back(Ans{(a[1]-1)/k+1,1,2});        return 1;    }    d[0][0] = 1;    for (int i = 1; i <= n; i++) {        for (int j = 0; j <= k; j++) {            if (d[i-1][j]) d[i][j] = 1, pre[i][j] = j;            else if (d[i-1][(j-b[i]+k)%k])                d[i][j] = 1, pre[i][j] = (j-b[i]+k)%k;        }    }    if (!d[n][v%k]) return 0;    for (int i = n, j = v%k; i >= 1; j = pre[i][j], i--) {        if (pre[i][j] != j) used[i] = 1;    }    int chose = 0;    for (int i = 1; i <= n; i++) {        if (used[i]) chose = i;    }    for (int i = 1; i <= n; i++){        if (chose && i != chose && used[i]) {            ans.push_back(Ans{(a[i]-1)/k+1, i, chose});            used[i] = 0;            a[chose] += a[i];            a[i] = 0;        }    }    int nchose = 0;    for (int i = 1; i <= n; i++) {        if (!used[i]) nchose = i;    }    for (int i = 1; i <= n; i++) {        if (nchose && i != nchose && a[i] && !used[i]) {            ans.push_back(Ans{(a[i]-1)/k+1, i, nchose});            a[nchose] += a[i];            a[i] = 0;        }    }    if (!chose) chose = 1;    if (a[chose] + a[nchose] < v) return 0;    if (a[chose] > v)        ans.push_back(Ans{(a[chose]-v)/k, chose, nchose});    else if (a[chose] < v)        ans.push_back(Ans{(v-a[chose])/k, nchose, chose});    return 1;}int main() {    scanf("%d%d%d", &n, &k, &v);    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i]%k;    if (!solve()) puts("NO");    else {        puts("YES");        for (auto a : ans) printf("%d %d %d\n", a.cnt, a.x, a.y);    }}
      
     

　　

E:

/*CodeForces 920E - Connected Components? [ 并查集 ]用并查集跳过不用继续查询的连续区间*/#include 
     
      using namespace std;typedef pair
      
        P;const int N = 200005;int n, m;vector
       
         ans;map
        
          mp;int f[N];int sf(int x) {    return x == f[x] ? x : f[x] = sf(f[x]);}int fa[N];queue
         
           Q;int BFS(int st) {    int res = 0;    while (!Q.empty()) Q.pop();    Q.push(st);    fa[st] = st;    f[st] = sf(st+1);    res++;    while (!Q.empty())    {        int u = Q.front(); Q.pop();        for (int v = sf(1); v <= n; v = sf(v+1))        {            if (mp[P(u,v)] || v == u) continue;            fa[v] = st;            f[v] = sf(v+1);            res++;            Q.push(v);        }    }    return res;}int main() {    scanf("%d%d", &n, &m);    for (int i = 1; i <= m; i++) {        int u, v; scanf("%d%d", &u, &v);        mp[P(u, v)] = mp[P(v, u)] = 1;    }    for (int i = 1; i <= n+1; i++) f[i] = i;    for (int i = 1; i <= n; i++)        if (!fa[i]) ans.push_back(BFS(i));    sort(ans.begin(), ans.end());    printf("%d\n", ans.size());    for (int i = 0; i < ans.size()-1; i++) printf("%d ", ans[i]);    printf("%d\n", ans[ans.size()-1]);}
         
        
       
      
     

F:

/*CodeForces 920F - SUM and REPLACE [ 线段树 ]D(n)下降快，不动点有两个，下降至不动点时不更新即可*/#include 
     
      using namespace std;#define LL long longconst int N = 3e5+5;const int M = 1e6+5;int n, m;int a[N];int D[M];void init() {    for (int i = 1; i < M; i++)        for (int j = i; j < M; j += i)            D[j]++;}LL sum[N<<2], Max[N<<2];void up(int x) {    sum[x] = sum[x<<1] + sum[x<<1|1];    Max[x] = max(Max[x<<1], Max[x<<1|1]);}void build(int l, int r, int x) {    if (l == r) {        sum[x] = Max[x] = a[l]; return;    }    int mid = (l+r) >> 1;    build(l, mid, x<<1); build(mid+1, r, x<<1|1);    up(x);}void change(int L, int R, int l, int r, int x) {    if (L <= l && r <= R && Max[x] == 1 || Max[x] == 2) return;    if (l == r) {        sum[x] = Max[x] = D[sum[x]];        return;    }    int mid = (l+r)>>1;    if (L <= mid) change(L, R, l, mid, x<<1);    if (mid < R) change(L, R, mid+1, r, x<<1|1);    up(x);}LL query(int L, int R, int l, int r, int x) {    if (L <= l && r <= R) return sum[x];    int mid = (l+r) >> 1;    LL res = 0;    if (L <= mid) res += query(L, R, l, mid, x<<1);    if (R > mid) res += query(L, R, mid+1, r, x<<1|1);    return res;}int main() {    init();    scanf("%d%d", &n, &m);    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);    build(1, n, 1);    while (m--)    {        int t, l, r;        scanf("%d%d%d", &t, &l, &r);        if (t == 1) change(l, r, 1, n, 1);        else printf("%lld\n", query(l, r, 1, n, 1));    }}
     

G:

/*CodeForces 920G - List Of Integers [ 容斥,二分 ]二分找答案，计算用容斥*/#include 
     
      using namespace std;const int N = 1e6+5;bool notp[N];int prime[N], pnum, mu[N];void Mobius() {    memset(notp, 0, sizeof(notp));    mu[1] = 1;    for (int i = 2; i < N; i++) {        if (!notp[i]) prime[++pnum] = i, mu[i] = -1;        for (int j = 1; prime[j]*i < N; j++) {            notp[prime[j]*i] = 1;            if (i%prime[j] == 0) {                mu[prime[j]*i] = 0;                break;            }            mu[prime[j]*i] = -mu[i];        }    }}int t, x, p, k;int Cal(int l, int r) {    int res = 0;    for (int i = 1; i*i <= p; i++) {        if (p%i == 0) {            res += mu[i] * (r/i-(l-1)/i);            if (p/i != i) res += mu[p/i] * (r/(p/i) - (l-1)/(p/i));        }    }    return res;}int BinaryFind(int l, int r, int k) {    while (l <= r) {        int mid = (l+r) >> 1;        if (Cal(x+1, mid) < k) l = mid+1;        else r = mid-1;    }    return l;}int main() {    Mobius();    scanf("%d", &t);    while (t--) {        scanf("%d%d%d", &x, &p, &k);        printf("%d\n", BinaryFind(x+1, 1e8, k));    }}