QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#635948 | #6512. Completely Multiplicative Function | HTensor# | WA | 7ms | 14240kb | C++23 | 2.5kb | 2024-10-12 21:33:40 | 2024-10-12 21:33:41 |
Judging History
answer
#include <bits/stdc++.h>
#define dd(x) cout << #x << "\n"
#define d(x) cout << #x << ": " << x << "\n"
#define SZ(x) ((int)(x).size())
using namespace std;
#define int long long
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using a3 = array<int, 3>;
using ll = long long;
const int inf = 0x3f3f3f3f3f3f3f3fLL;
#define MULTI_TEST
const int N = 1e6 + 6;
int isnt[N], ist[N], f[N];
vector<int> prime, p2;
int px[N];
void sieve(int n) {
isnt[1] = isnt[0] = 1;
for(int i = 2; i <= n; i++) {
if(!isnt[i]) prime.push_back(i);
for(auto p : prime) {
if(i * p > n) break;
isnt[i * p] = 1;
if(i % p == 0) break;
}
}
}
void calc(int n) {
f[1] = 1;
ist[1] = ist[0] = 1;
for(int i = 2; i <= n; i++) {
if(!ist[i]) prime.push_back(i);
for(auto p : prime) {
if(i * p > n) break;
ist[i * p] = 1;
if(p >= 71) f[i * p] = f[i];
else f[i * p] = f[i] * px[p];
if(i % p == 0) break;
}
};
}
void clear(int n) {
for(int i = 1; i <= n; i++) {
f[i] = 1;
ist[1] = 0;
}
}
void solve() {
int n, k; cin >> n >> k;
if((k + n) & 1) {
cout << "-1" << "\n";
return ;
}
clear(n);
for(int i = 1; i <= n; i++) px[i] = 1;
int cnt = 0;
for(int i = n / 2 + 1; i <= n; i++) {
if(!isnt[i]) ++cnt;
}
vector<int> pp{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};
for(int i = 0; i < 20; i++) {
px[i] = -1;
calc(n);
int now = 0;
for(int i = 1; i <= n; i++) now += f[i];
clear(n);
if(now < k) {
px[i] = 1;
}
}
calc(n);
int now = 0;
for(int i = 1; i <= n; i++) now += f[i];
if((now - k) / 2 > cnt) assert(false);
else if(cnt) {
for(int i = 1; i <= n; i++) {
if(i >= n / 2 + 1 && !isnt[i]) {
f[i] = -1;
cnt -= 2;
if(cnt <= 0) break;
}
}
}
for(int i = 1; i <= n; i++) {
cout << f[i] << " ";
}
clear(n);
cout << "\n";
}
signed main() {
sieve(1e6);
ios::sync_with_stdio(false); cin.tie(0);
#ifdef MULTI_TEST
int T; cin >> T;
#else
int T = 1;
#endif
while(T--) solve();
return 0;
}
/*
4
4 2
10 0
10 1
10 10
*/
详细
Test #1:
score: 0
Wrong Answer
time: 7ms
memory: 14240kb
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:
wrong answer sum of f is not k (test case 1)