QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #547710 | #6512. Completely Multiplicative Function | rotcar07 | WA | 27ms | 7728kb | C++14 | 807b | 2024-09-05 08:13:53 | 2024-09-05 08:13:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int maxn=1e6+5;
int f[maxn],pr[maxn],g[maxn];
int main(){
int t;cin>>t;
while(t--){
int n,k;cin>>n>>k;
if((n-k)&1){cout<<"-1\n";continue;}
for(int i=1;i<=n;i++) g[i]=f[i]=1,pr[i]=0;
int cur=n;
for(int i=2;i<=n;i++)if(!pr[i]){
int cnt=cur-g[i]*2;g[i]=-g[i];
for(int j=i+i;j<=n;j+=i){
cnt-=g[j];g[j]=g[j/i]*g[i];
cnt+=g[j];
}
if(abs(cur-k)>abs(cnt-k)){
for(int j=i;j<=n;j+=i) f[j]=g[j];
cur=cnt;
}
else{
for(int j=i;j<=n;j+=i) g[j]=f[j];
}
}
for(int i=1;i<=n;i++) cout<<f[i]<<' ';cout<<'\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7728kb
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
Wrong Answer
time: 27ms
memory: 7676kb
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 ...
result:
wrong answer f[4] != f[2] * f[2] (test case 21)