# 3 月 19 日测试题解()-其他

## 3 月 19 日测试题解()

### 题意

• 设 $$a > b$$，否则交换 $$a$$ 与 $$b$$，然后让 $$a$$ 减去 $$b$$。

$$a, b \le 10^{18}$$。

### $$\text{100pts}$$

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
i64 a, b;
std::cin >> a >> b;

i64 ans = 0;
while (a != b) {
if (a < b) {
std::swap(a, b);
}
if (a % b == 0) {
ans += a / b - 1;
break;
}
ans += a / b;
a -= a / b * b;
}
std::cout << ans << "\n";

return;
}

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);

int t;
std::cin >> t;

while (t--) {
solve();
}

return 0;
}


### $$\text{100pts}$$

#include <bits/stdc++.h>

using i64 = long long;

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);

int n;
std::cin >> n;

std::vector<std::vector<int>> a(5, std::vector<int>(n));
for (int i = 0; i < 5; i++) {
for (int j = 0; j < n; j++) {
std::cin >> a[i][j];
}
}

std::unordered_set<int> sum1, sum2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int cur = a[0][i] + a[1][j];
sum1.insert(cur);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int cur = a[2][i] + a[3][j];
sum2.insert(cur);
}
}

for (auto i : sum1) {
for (auto j : sum2) {
for (auto k : a[4]) {
if (i + j + k == 0) {
std::cout << "YES\n";
return 0;
}
}
}
}
std::cout << "NO\n";

return 0;
}


### $$\text{40pts}$$

• $$\sum_{j \in a} j < 2^k$$
• 至少存在一对 $$p$$ 与 $$q$$ 使得 $$a_p = a_q$$ 并且 $$a_p \ge a_m$$。

### $$\text{100pts}$$

#include <bits/stdc++.h>

using i64 = long long;

i64 fastPow(i64 base, i64 pow, i64 mod) {
i64 res = 1;
while (pow) {
if (pow & 1) {
(res *= base) %= mod;
}
(base *= base) %= mod;
pow >>= 1;
}
return res;
}

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);

static const int MOD = 998244353, M = 1 << 11;

int n;
std::cin >> n;

std::vector<int> a;
int rst = 0;
for (int i = 0; i < n; i++) {
int cur;
std::cin >> cur;
if (__builtin_popcount(cur) == 1) {
a.push_back(cur);
} else {
rst++;
}
}

if (!a.size()) {
std::cout << 0 << "\n";
return 0;
}

std::vector<int> f(M + 1);
f[0] = 1;
for (int i = 0; i < a.size(); i++) {
for (int j = M; j >= a[i]; j--) {
(f[j] += f[j - a[i]]) %= MOD;
}
}
for (int i = 1; i <= M; i++) {
(f[i] += f[i - 1]) %= MOD;
}

i64 ans = (fastPow(2, a.size(), MOD) - f[M - 1] + MOD) % MOD;
(ans *= fastPow(2, rst, MOD)) %= MOD;
std::cout << ans << "\n";

return 0;
}

————————

### 题意

• 设 $$a > b$$，否则交换 $$a$$ 与 $$b$$，然后让 $$a$$ 减去 $$b$$。

$$a, b \le 10^{18}$$。

### $$\text{100pts}$$

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
i64 a, b;
std::cin >> a >> b;

i64 ans = 0;
while (a != b) {
if (a < b) {
std::swap(a, b);
}
if (a % b == 0) {
ans += a / b - 1;
break;
}
ans += a / b;
a -= a / b * b;
}
std::cout << ans << "\n";

return;
}

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);

int t;
std::cin >> t;

while (t--) {
solve();
}

return 0;
}


### $$\text{100pts}$$

#include <bits/stdc++.h>

using i64 = long long;

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);

int n;
std::cin >> n;

std::vector<std::vector<int>> a(5, std::vector<int>(n));
for (int i = 0; i < 5; i++) {
for (int j = 0; j < n; j++) {
std::cin >> a[i][j];
}
}

std::unordered_set<int> sum1, sum2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int cur = a[0][i] + a[1][j];
sum1.insert(cur);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int cur = a[2][i] + a[3][j];
sum2.insert(cur);
}
}

for (auto i : sum1) {
for (auto j : sum2) {
for (auto k : a[4]) {
if (i + j + k == 0) {
std::cout << "YES\n";
return 0;
}
}
}
}
std::cout << "NO\n";

return 0;
}


### $$\text{40pts}$$

• $$\sum_{j \in a} j < 2^k$$
• 至少存在一对 $$p$$ 与 $$q$$ 使得 $$a_p = a_q$$ 并且 $$a_p \ge a_m$$。

### $$\text{100pts}$$

#include <bits/stdc++.h>

using i64 = long long;

i64 fastPow(i64 base, i64 pow, i64 mod) {
i64 res = 1;
while (pow) {
if (pow & 1) {
(res *= base) %= mod;
}
(base *= base) %= mod;
pow >>= 1;
}
return res;
}

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);

static const int MOD = 998244353, M = 1 << 11;

int n;
std::cin >> n;

std::vector<int> a;
int rst = 0;
for (int i = 0; i < n; i++) {
int cur;
std::cin >> cur;
if (__builtin_popcount(cur) == 1) {
a.push_back(cur);
} else {
rst++;
}
}

if (!a.size()) {
std::cout << 0 << "\n";
return 0;
}

std::vector<int> f(M + 1);
f[0] = 1;
for (int i = 0; i < a.size(); i++) {
for (int j = M; j >= a[i]; j--) {
(f[j] += f[j - a[i]]) %= MOD;
}
}
for (int i = 1; i <= M; i++) {
(f[i] += f[i - 1]) %= MOD;
}

i64 ans = (fastPow(2, a.size(), MOD) - f[M - 1] + MOD) % MOD;
(ans *= fastPow(2, rst, MOD)) %= MOD;
std::cout << ans << "\n";

return 0;
}