QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #787853 | #6512. Completely Multiplicative Function | OIer_kzc# | WA | 28ms | 12648kb | C++20 | 2.8kb | 2024-11-27 14:57:02 | 2024-11-27 14:57:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int prime[100005],to[1000005],f[1000005];
bool no[1000005];
using ll=long long;
#define endl '\n'
int main(){
int t;cin>>t;
no[1]=1;
int cnt=0;
for(int i=2;i<1000001;i++){
if(!no[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&prime[j]*i<1000001;j++){
no[i*prime[j]]=1,to[i*prime[j]]=prime[j];
if(!(i%prime[j])) break;
}
}
f[1]=1;
// int k=15,n=40;
// cout<<prime[15]<<endl;
// for(int i=1;i<1<<k;i++){
// for(int j=1;j<=k;j++) if(i>>j-1&1) f[prime[j]]=1;else f[prime[j]]=-1;
// for(int j=4;j<=n;j++) if(no[j]) f[j]=f[j/to[j]]*f[to[j]];
// int sum=0;
// for(int j=1;j<=n;j++) sum+=f[j];
// if(sum==0){
// for(int j=1;j<=n;j++) cout<<f[j]<<' ';cout<<endl;
// return 0;
// }
// }
while(t--){
int n,k,tmp;cin>>n>>k,tmp=k;
if((n^k)&1){
cout<<"-1\n";continue;
}
if(n==16&&!k){
cout<<"1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 -1 1 -1 1\n";
continue;
}
if(n==18&&!k){
cout<<"1 1 -1 1 1 -1 -1 1 1 1 -1 -1 -1 -1 -1 1 -1 1\n";
continue;
}
if(n==35&&k==1){
cout<<"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\n";
continue;
}
if(n==36&&!k){
cout<<"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\n";
continue;
}
if(n==37&&k==1){
cout<<"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\n";
continue;
}
if(n==38&&!k){
cout<<"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\n";
continue;
}
if(n==40&&!k){
cout<<"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\n";
continue;
}
k=n-k>>1;
for(int i=1;i<=cnt&&prime[i]<=n;i++) if((ll)prime[i]*prime[i+1]>n&&k>=n/prime[i]-((ll)prime[i]*prime[i]<=n)){
k-=n/prime[i]-((ll)prime[i]*prime[i]<=n),f[prime[i]]=-1;
}
else f[prime[i]]=1;
for(int i=4;i<=n;i++) if(no[i]) f[i]=f[i/to[i]]*f[to[i]];
int sum=0;
for(int i=1;i<=n;i++) sum+=f[i],cout<<f[i]<<' ';
//assert(sum==tmp);
cout<<endl;
}
// for(int n=1;n<1000001;n++){
// int ans=0;
// for(int i=1;i<=cnt&&prime[i]<=n;i++) if((ll)prime[i]*prime[i+1]>n) ans+=n/prime[i]-((ll)prime[i]*prime[i]<=n);
// if(ans<n/2) cout<<n<<' '<<ans<<endl;
// }
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 10328kb
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: 28ms
memory: 12648kb
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 sum of f is not k (test case 668)