QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#177915 | #6512. Completely Multiplicative Function | mendicillin2# | RE | 7ms | 8340kb | C++17 | 2.4kb | 2023-09-13 15:52:01 | 2023-09-13 15:52:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using ll = int64_t;
using vi = vc<int>;
template <class F>
struct ycr {
F f;
template <class T>
explicit ycr(T&& f_) : f(forward<T>(f_)) {}
template <class... Args>
decltype(auto) operator()(Args&&... args) {
return f(ref(*this), forward<Args>(args)...);
}
};
template <class F>
decltype(auto) yc(F&& f) {
return ycr<decay_t<F>>(forward<F>(f));
}
const int MAXN = 1.1e6;
vi ps;
int pri[MAXN];
const int L = 30;
vector<int> prec[L+1][L+1];
void precomp() {
fill(pri + 2, pri + MAXN, 0);
for (int a = 2; a * a < MAXN; a++) {
if (pri[a]) continue;
for (int b = 2*a; b < MAXN; b += a) {
if (!pri[b]) pri[b] = a;
}
}
for (int a = 2; a < MAXN; a++) {
if (pri[a] == 0) ps.push_back(a);
}
prec[1][1] = {1, 1};
for (int n = 2; n <= L; n++) {
vector<int> cur_ps;
for (int p : ps) {
if (p <= n) {
cur_ps.push_back(p);
} else {
break;
}
}
int num = int(cur_ps.size());
for (int m = 0; m < (1 << num); m++) {
vector<int> f(n+1, 0);
f[1] = 1;
for (int i = 0; i < num; i++) {
int p = cur_ps[i];
if (m & (1 << i)) {
f[p] = 1;
} else {
f[p] = -1;
}
}
int cur_k = 0;
for (int a = 1; a <= n; a++) {
if (f[a] == 0) {
assert(pri[a] != 0);
f[a] = f[a / pri[a]] * f[pri[a]];
assert(abs(f[a]) == 1);
}
cur_k += f[a];
}
assert(abs(cur_k) <= n);
if (cur_k >= 0) {
prec[n][cur_k] = f;
}
}
}
}
vector<int> solve(int N, int K) {
if (N <= L) return prec[N][K];
if ((N-K) % 2) return {};
int need = (N-K) / 2;
vector<int> res(N+1, 1);
for (int p : ps) {
if (p * p <= N) continue;
if (p > N) break;
int c = N/p;
if (c <= need) {
for (int a = p; a <= N; a += p) {
res[a] = -1;
}
need -= c;
}
}
assert(need == 0);
return res;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(20);
precomp();
int T; cin >> T;
while (T--) {
int N, K; cin >> N >> K;
auto res = solve(N, K);
if (res.empty()) {
cout << -1 << '\n';
} else {
assert(int(res.size()) == N+1);
assert(accumulate(res.begin() + 1, res.end(), 0) == K);
for (int i = 1; i <= N; i++) {
assert(abs(res[i]) == 1);
cout << res[i] << " \n"[i==N];
}
}
}
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 8340kb
input:
4 4 2 10 0 10 1 10 10
output:
1 -1 1 1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 1 1 1 1 1 1 1 1 1 1
result:
ok ok (4 test cases)
Test #2:
score: -100
Runtime Error
input:
11475 1 0 1 1 2 0 2 1 2 2 3 0 3 1 3 2 3 3 4 0 4 1 4 2 4 3 4 4 5 0 5 1 5 2 5 3 5 4 5 5 6 0 6 1 6 2 6 3 6 4 6 5 6 6 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 8 0 8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8 9 0 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 10 0 10 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 11 0 11 1 11 2 11 3 11...
output:
-1 1 1 -1 -1 1 1 -1 1 -1 1 -1 1 1 1 1 -1 -1 1 -1 1 -1 1 1 -1 1 1 1 1 -1 1 -1 -1 1 1 -1 1 -1 1 1 1 -1 1 1 1 1 1 1 -1 1 1 -1 -1 -1 1 -1 1 1 1 -1 -1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 -1 -1 1 -1 -1 1 -1 1 1 1 -1 1 -1 -1 1 1 -1 ...