QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#243767#6512. Completely Multiplicative FunctionDelay_for_five_minutes#WA 1329ms12792kbC++201.5kb2023-11-08 17:01:572023-11-08 17:01:59

Judging History

你现在查看的是最新测评结果

  • [2023-11-08 17:01:59]
  • 评测
  • 测评结果:WA
  • 用时:1329ms
  • 内存:12792kb
  • [2023-11-08 17:01:57]
  • 提交

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)