链接：https://ac.nowcoder.com/acm/contest/21592
B
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int x, y;
cin >> x >> y;
int cnt = 0;
vector<int> ans;
while (1) {
int g = gcd(x, y);
x /= g;
y /= g;
int d = x / y;
ans.push_back(d);
int tmp = x % y;
x = y;
y = tmp;
cnt++;
if (y == 1) {
ans.push_back(x);
break;
}
}
cout << cnt << ' ';
for (int i = 0; i < (int) ans.size(); i++) {
cout << ans[i] << " \n"[i == (int) ans.size() - 1];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
F
Python Code
import sys
input = sys.stdin.buffer.readline
f = [0] * 10001
f[1] = 1
cnt = add = 2
j = 0
for i in range(2, 10001):
f[i] = f[i - 1] + add
j += 1
if j == cnt:
cnt += 1
j = 0
add *= 2
for _ in range(int(input())):
n = int(input())
print(f[n])
G
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int N = 1E6;
vector<int> minp, primes;
void sieve(int n) {
minp.assign(n + 1, 0);
for (int i = 2; i <= n; i++) {
if (minp[i] == 0) {
minp[i] = i;
primes.push_back(i);
}
for (auto p : primes) {
if (i * p > n) {
break;
}
minp[i * p] = p;
if (p == minp[i]) {
break;
}
}
}
}
vector<vector<int>> fac(N + 1);
int cnt[N + 1], k[N + 1];
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
if (fac[a[i]].empty()) {
int x = a[i];
while (x > 1) {
int p = minp[x];
x /= p;
if (fac[a[i]].empty() || p != fac[a[i]].back()) {
fac[a[i]].push_back(p);
}
}
}
}
struct node {
int l, r, i;
};
vector<node> q(m);
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
l--;
r--;
q[i] = {l, r, i};
}
int bk = sqrt(n);
sort(q.begin(), q.end(), [&](node a, node b) {
return ((a.l / bk) ^ (b.l / bk)) ? a.l < b.l : (((a.l / bk) & 1) ? a.r < b.r : a.r > b.r);
});
int l = 0, r = -1;
int res = 0;
vector<int> ans(n);
auto add = [&](int j) {
int num = a[j];
for (auto &x : fac[num]) {
cnt[x]++;
k[cnt[x]]++;
if (k[cnt[x]] == 1) {
res++;
}
}
};
auto del = [&](int j) {
int num = a[j];
for (auto &x : fac[num]) {
k[cnt[x]]--;
if (k[cnt[x]] == 0) {
res--;
}
cnt[x]--;
}
};
for (int i = 0; i < m; i++) {
auto &[ql, qr, qid] = q[i];
while (r < qr) add(++r);
while (l > ql) add(--l);
while (l < ql) del(l++);
while (r > qr) del(r--);
ans[qid] = res;
}
while (l <= r) {
del(l++);
}
for (int i = 0; i < m; i++) {
cout << ans[i] << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
sieve(N);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
H
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, k;
cin >> n >> k;
if (n == 1) {
cout << "freesin\n";
return;
}
if (n - 1 - k <= 0) {
cout << "pllj\n";
return;
}
cout << "freesin\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
J
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int l = 1, r = n + 1;
int ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
auto check = [&](int x) {
set<pair<int, int>> s;
unordered_map<int, int> mp;
int res = 0;
for (int i = 0; i < n; i++) {
if (mp.count(a[i])) {
res++;
s.erase({mp[a[i]], a[i]});
mp[a[i]] = i + 1;
s.insert({i + 1, a[i]});
continue;
}
if ((int) s.size() == x) {
auto it = s.begin();
mp.erase(it->second);
s.erase(it);
}
mp[a[i]] = i + 1;
s.insert({i + 1, a[i]});
}
return res >= k;
};
if (check(mid)) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
if (ans == -1) {
cout << "cbddl\n";
} else {
cout << ans << '\n';
}
return 0;
}
K
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n, m;
cin >> n >> m;
cout << 1LL * n * (n + 1) * (2 * n + 1) / 6 * m << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
L
C++ Code
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int N = 100000;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(N + 1);
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
a[x1]++;
a[x2]--;
}
for (int i = 1; i <= N; i++) {
a[i] += a[i - 1];
}
int ans = 0;
for (int i = 0; i <= N; i++) {
if (a[i] > 0) {
ans++;
}
}
cout << ans << '\n';
return 0;
}