QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #179014 | #6512. Completely Multiplicative Function | linzi# | WA | 27ms | 15340kb | C++17 | 1.1kb | 2023-09-14 16:37:18 | 2023-09-14 16:37:18 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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)