QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#243767 | #6512. Completely Multiplicative Function | Delay_for_five_minutes# | WA | 1329ms | 12792kb | C++20 | 1.5kb | 2023-11-08 17:01:57 | 2023-11-08 17:01:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
const int N=1e6+3;
int pri[N],cnt,p[N];
bool np[N];
void sieve(int n){
for(int i=2;i<=n;++i){
if(!np[i])pri[++cnt]=i,p[i]=i;
for(int j=1;j<=cnt&&i*pri[j]<=n;++j){
p[i*pri[j]]=pri[j];
np[i*pri[j]]=1;
if(!(i%pri[j]))break;
}
}
}
int n,k,mg,f[N],s[N];
bool flag;
void large(){
int now=0;
for(int i=1;i<=n;++i){
int x=i,pr=1;
while(x>1)pr*=f[p[x]],x/=p[x];
if(pr)f[i]=pr,now+=pr;
//cout<<"f["<<i<<"]="<<f[i]<<'\n';
}
for(int i=1;i*i<=n||i<=pri[mg];++i)s[i]=s[i-1]+f[i];
for(int i=mg+1;pri[i]<=n;++i){
int sum=s[n/pri[i]];
if(sum>=0&&now<=k||sum<0&&now>k)f[pri[i]]=1,now+=sum;
else f[pri[i]]=-1,now-=sum;
}
if(now==k){
for(int i=1;i<=n;++i)if(!f[i]){
int x=i,pr=1;
while(x>1)pr*=f[p[x]],x/=p[x];
f[i]=pr;
}
flag=1;
}
}
void dfs(int k){
if(k>mg){
large();
return;
}
f[pri[k]]=1;
dfs(k+1);
if(flag)return;
f[pri[k]]=-1;
dfs(k+1);
}
void solve(){
cin>>n>>k;
if((k+n)&1){
cout<<"-1\n";
return;
}
f[1]=1;
mg=10;
while(pri[mg]*pri[mg]<n)++mg;
while(pri[mg]>n)--mg;
if(n<=1000){
flag=0;
dfs(1);
if(flag){
for(int i=1;i<=n;++i)cout<<f[i]<<' ';
cout<<'\n';
}
else{
cout<<"-1\n";
}
}
else{
for(int i=1;i<=mg;++i)f[pri[i]]=1;
large();
for(int i=1;i<=n;++i)cout<<f[i]<<' ';
cout<<'\n';
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
sieve(1e6);
int T;
cin>>T;
while(T--)solve();
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 12792kb
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: 1329ms
memory: 10936kb
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 ans finds the answer, but out doesn't (test case 497)