QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#179014#6512. Completely Multiplicative Functionlinzi#WA 27ms15340kbC++171.1kb2023-09-14 16:37:182023-09-14 16:37:18

Judging History

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

  • [2023-09-14 16:37:18]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:15340kb
  • [2023-09-14 16:37:18]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define inf 1e18
#define mn 1000005
using namespace std;
ll ans,vis[mn],p[mn],a[mn],cnt=0,n,m,lim;
void prim(ll n)
{ll i,j;
	vis[1]=1;//1不是质数
	for(i=2;i<=n;i++)
	{
		if(vis[i]==0)//vis[i]==0的就是质数
		{
			p[++cnt]=i;
		}
		for(j=1;j<=cnt&&i*p[j]<=n;j++)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
}
int main()
{
	ll t,x,y,z,i,j,k;
	prim(1e6);
	cin>>t;
	while(t--)
	{
		scanf("%lld%lld",&n,&m);
		if((n-m)%2==1){puts("-1");continue;}
		for(i=1;i<=n;i++)
			a[i]=1;
		lim=(n-m)/2;
		ll sum=0,tmp;
		for(i=1;p[i]<=n&&sum<lim&&i<=cnt;i++)
		{	
			x=p[i];
			tmp=0;
			while(x<=n)
			{
				for(j=x;j<=n;j+=x)
				{
					a[j]*=-1;
					tmp-=a[j];
				}
				x*=p[i];
			}
			if(tmp<0)
			{
				x=p[i];
				while(x<=n)
				{
					for(j=x;j<=n;j+=x)
					{
						a[j]*=-1;
					}
					x*=p[i];
				}
			}
			else 
			{
				if(sum+tmp>lim)continue;
				else sum+=tmp;
			}
		}
		if(sum==lim)
		{
			for(i=1;i<=n;i++)
				printf("%lld ",a[i]);
			puts("");
		}
		else puts("-1");
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 15340kb

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: 13896kb

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 ...

result:

wrong answer sum of f is not k (test case 25)