D:
/*
CodeForces 920D - Tanks [ DP ]
核心思想是判断是否能用 a[i]%k 来构成 V%k
DP并记录路径即可，剩下的就是加K减K操作
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const 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> 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
", a.cnt, a.x, a.y);
}
}
E:
/*
CodeForces 920E - Connected Components? [ 并查集 ]
用并查集跳过不用继续查询的连续区间
*/
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int N = 200005;
int n, m;
vector<int> ans;
map<P, int> mp;
int f[N];
int sf(int x) {
return x == f[x] ? x : f[x] = sf(f[x]);
}
int fa[N];
queue<int> 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
", ans.size());
for (int i = 0; i < ans.size()-1; i++) printf("%d ", ans[i]);
printf("%d
", ans[ans.size()-1]);
}
F:
/*
CodeForces 920F - SUM and REPLACE [ 线段树 ]
D(n)下降快，不动点有两个，下降至不动点时不更新即可
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const 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
", query(l, r, 1, n, 1));
}
}
G:
/*
CodeForces 920G - List Of Integers [ 容斥,二分 ]
二分找答案，计算用容斥
*/
#include <bits/stdc++.h>
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
", BinaryFind(x+1, 1e8, k));
}
}