E2. Divisible Numbers (hard version)
用 pollard rho 跑出 \(ab\) 的质因数分解，然后 dfs 枚举 \(ab\) 的所有因子对 \(x, y\)，如果存在 \(k_1, k_2\) 使得 \(a < k_1x \le c\) 且 \(b < k_2y \le d\)，那么 \(k_1x\) 和 \(k_2y\)就是一个可行解。
复杂度没算，问就是能过。
AC代码
// Problem: E2. Divisible Numbers (hard version)
// Contest: Codeforces - Codeforces Round #828 (Div. 3)
// URL: https://codeforces.com/contest/1744/problem/E2
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define CPPIO \
std::ios::sync_with_stdio(false); \
std::cin.tie(0); \
std::cout.tie(0);
#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#define ASSERT(x) ;
#define serialize() std::string("")
#endif
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
void Initialize();
void SolveCase(int Case);
int main(int argc, char* argv[]) {
CPPIO;
Initialize();
int T = 1;
std::cin >> T;
for (int t = 1; t <= T; ++t) {
SolveCase(t);
}
return 0;
}
void Initialize() {}
namespace PollardRho {
/**
* @TODO: __int128_t is ugly, try optimize it.
*/
static std::mt19937_64 rng_(
std::chrono::steady_clock::now().time_since_epoch().count());
inline int64_t Rand(int64_t l, int64_t r) {
return l + rng_() % (r - l + 1);
}
inline int64_t Add(int64_t a, int64_t b, int64_t mod) {
return ((__int128_t)a + b) % mod;
}
inline int64_t Substract(int64_t a, int64_t b, int64_t mod) {
return (((__int128_t)a - b) % mod + mod) % mod;
}
inline int64_t Multiply(int64_t a, int64_t b, int64_t mod) {
return (__int128_t)a * b % mod;
}
inline int64_t Power(int64_t a, int64_t b, int64_t mod) {
int64_t r = 1;
while (b) {
if (b & 1)
r = Multiply(r, a, mod);
a = Multiply(a, a, mod);
b >>= 1;
}
return r;
}
// Time Complexity: $O(k \log^{3} n)$
bool MillerRabinTest(int64_t n) {
// Strong enough for $n < 2^64$, see https://oeis.org/A014233.
constexpr static int kTestRounds = 12;
constexpr static int kTestBase[kTestRounds] = {2, 3, 5, 7, 11, 13,
17, 19, 23, 29, 31, 37};
if (n <= kTestBase[kTestRounds - 1]) {
return *std::lower_bound(kTestBase, kTestBase + kTestRounds, n) == n;
}
int64_t d = n - 1, r = 0;
while (d % 2 == 0) {
d >>= 1;
r = r + 1;
}
for (int round = 0; round < kTestRounds; ++round) {
int64_t a = kTestBase[round];
// Fermet primality test.
int64_t x = Power(a, d, n);
if (x == 1 || x == n - 1)
continue;
// Witness primality test.
for (int i = 0; i < r - 1; ++i) {
x = Multiply(x, x, n);
if (x == n - 1)
break;
}
if (x != n - 1)
return false;
}
return true;
}
int64_t Rho(int64_t n) {
// Can not factor 4 because the faster step gap is 2.
if (n == 4)
return 2;
const static int kMaxStepSize = 1 << 7;
int64_t c;
std::function<int64_t(int64_t)> f = [&n, &c](int64_t x) {
return Add(Multiply(x, x, n), c, n);
};
// Since n is not a prime, there must be a non-trivial factor of n.
for (;;) {
/**
* Brent's cycle finding method, and replace k gcd steps with k - 1
* multiplications modulo n and a single gcd. reference:
* https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm#Variants.
*/
c = Rand(3, n - 1);
int64_t x = Rand(0, n - 1);
int64_t t = f(x), r = f(t);
int64_t goal = 1, curr = 1;
int64_t d1, d2 = 1;
while (t != r) {
d1 = Multiply(d2, std::abs(r - t), n);
if (d1 == 0) {
break;
} else {
d2 = d1;
}
if (curr % kMaxStepSize == 0) {
int64_t d = std::gcd(d2, n);
if (d != 1 && d != n)
return d;
}
if (curr == goal) {
int64_t d = std::gcd(d2, n);
if (d != 1 && d != n)
return d;
t = r;
goal = goal * 2;
curr = 0;
}
r = f(r);
++curr;
}
}
}
std::vector<std::pair<int64_t, int64_t>> Factor(int64_t n) {
std::vector<std::pair<int64_t, int64_t>> factors;
std::function<void(int64_t)> factor = [&](int64_t n) {
if (n < 2)
return;
if (MillerRabinTest(n)) {
factors.push_back({n, 0});
} else {
int64_t x = Rho(n);
while (n % x == 0)
n /= x;
factor(x);
factor(n);
}
};
factor(n);
std::sort(factors.begin(), factors.end());
factors.erase(std::unique(factors.begin(), factors.end()), factors.end());
for (auto& [p, e] : factors) {
while (n % p == 0) {
++e;
n /= p;
}
}
return factors;
}
}; // namespace PollardRho
std::mt19937 rng(time(0));
int rnd(int l, int r) {
return l + rng() % (r - l + 1);
}
void SolveCase(int Case) {
int a, b, c, d;
std::cin >> a >> b >> c >> d;
// a = rnd(1, 1e8), c = rnd(a + 1, 1e9);
// b = rnd(1, 1e8), d = rnd(a + 1, 1e9);
i64 ab = i64(1) * a * b;
if (ab == 1) {
std::cout << c << " " << d << "\n";
return;
}
auto pe = PollardRho::Factor(ab);
// logd(pe);
int rx = -1, ry = -1;
auto check = [&](i64 x, i64 y) {
i64 nx = c / x * x;
i64 ny = d / y * y;
if (nx > a && ny > b) {
rx = nx;
ry = ny;
return;
}
};
std::function<void(int, i64)> dfs = [&](int p, i64 x) {
if (rx != -1)
return;
check(x, ab / x);
check(ab / x, x);
if (p == pe.size())
return;
i64 y = 1;
for (int i = 0; i <= pe[p].second; ++i) {
dfs(p + 1, x * y);
y = y * pe[p].first;
}
};
dfs(0, 1);
if (rx != -1) {
i64 xy = i64(1) * rx * ry;
assert(a < rx && rx <= c);
assert(b < ry && ry <= d);
assert(xy % ab == 0);
}
std::cout << rx << " " << ry << "\n";
}
F. MEX vs MED
观察：\(\operatorname{mex}(p_l, p_{l + 1}, \dots, p_r) > \operatorname{med}(p_l, p_{l + 1}, \dots, p_r)\) 等价于 \(0, 1, \dots, \lfloor \frac{r - l}{2} \rfloor\) 都位于 \([l, r]\)。
根据观察可以推出，长度为 \(x\) 的区间要想符合答案，那么必须要有 \(0, 1, 2, \dots, \lfloor \frac{x - 1}{2} \rfloor\) 都位于区间内，即 \(0, 1, 2, \dots, x\) 仅对长度为 \(2x + 1\) 和长度为 \(2x + 2\) 的区间有贡献。
然后就是简单模拟了，即依次枚举\(x\)，计算出包含 \(0, 1, 2, \dots, x\) 的极小区间 \([l, r]\)，然后看有多少个长度为 \(2x + 1\) 的区间和长度为 \(2x + 2\) 包含 \([l, r]\).
AC代码
// Problem: F. MEX vs MED
// Contest: Codeforces - Codeforces Round #828 (Div. 3)
// URL: https://codeforces.com/contest/1744/problem/F
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define CPPIO \
std::ios::sync_with_stdio(false); \
std::cin.tie(0); \
std::cout.tie(0);
#ifdef BACKLIGHT
#include "debug.h"
#else
#define logd(...) ;
#define ASSERT(x) ;
#define serialize() std::string("")
#endif
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
void Initialize();
void SolveCase(int Case);
int main(int argc, char* argv[]) {
CPPIO;
Initialize();
int T = 1;
std::cin >> T;
for (int t = 1; t <= T; ++t) {
SolveCase(t);
}
return 0;
}
void Initialize() {}
void SolveCase(int Case) {
int n;
std::cin >> n;
std::vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
b[a[i]] = i;
}
auto calc = [&](int l, int r, int x) -> int {
logd(l, r, x);
int y = r - l + 1;
if (x < y)
return 0;
int right_bound = std::min(l, n - 1 - x + 1);
int left_bound = std::max(0, r - x + 1);
logd(l, r, x, right_bound, left_bound);
return right_bound - left_bound + 1;
};
i64 ans = 0;
int l = n, r = -1;
for (int i = 0; 2 * i + 1 <= n; ++i) {
l = std::min(l, b[i]);
r = std::max(r, b[i]);
ans += calc(l, r, 2 * i + 1);
if (2 * i + 2 <= n)
ans += calc(l, r, 2 * i + 2);
}
std::cout << ans << "\n";
}