QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#738409 | #9167. Coprime Array | ucup-team134# | WA | 896ms | 4156kb | C++14 | 2.0kb | 2024-11-12 18:59:49 | 2024-11-12 18:59:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> best;
vector<int> ans;
void Try(int s,int x,int sum){
/*if(__gcd(s,x)==1){
best={s};
}else if(__gcd(s-1,x)==1){
best={1,s-1};
}else if(__gcd(s-2,x)==1){
best={1,1,s-2};
}else{
assert(false);
}*/
if(sum==s){
if(best.empty() || best.size()>ans.size()){
best=ans;
}
return;
}
if(best.size()>0 && ans.size()>=best.size()){
return;
}
if(__gcd(s-sum,x)==1){
ans.pb(s-sum);
Try(s,x,s);
ans.pop_back();
return;
}
for(int i=1;i<s-sum;i++){
if(__gcd(i,x)==1){
ans.pb(i);
Try(s,x,sum+i);
ans.pop_back();
}
}
}
const int lim=1e7;
const int mx=1e9;
vector<int> Solve(int s,int x){
if(__gcd(s,x)==1)return {s};
for(int i=1;i<min(s,lim);i++){
if(__gcd(i,x)==1){
if(__gcd(s-i,x)==1){
return {i,s-i};
}
if(s+i<=mx && __gcd(s+i,x)==1){
return {-i,s+i};
}
}
}
int n=max(s,x);
for(int i=-n;i<=n;i++)if(__gcd(i,x)==1){
for(int j=-n;j<=n;j++)if(__gcd(j,x)==1){
int k=s-i-j;
if(__gcd(k,x)==1){
return {i,j,k};
}
}
}
assert(false);
}
mt19937 rng(time(0));
int main(){
//while(true){
int s,x;
scanf("%i %i",&s,&x);
vector<int> ans=Solve(s,x);
printf("%i\n",ans.size());
for(int x:ans)printf("%i ",x);printf("\n");
//s=rng()%10000+1;
//x=rng()%10000+1;
//printf("%i %i\n",s,x);
// best.clear();
//Try(s,x,0);
//if(best.size()>3){
//printf("%i\n",best.size());
// for(int x:best)printf("%i ",x);
// printf("\n");
//}
// }
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3876kb
input:
9 6
output:
3 -5 -5 19
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
14 34
output:
2 1 13
result:
ok Correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
1000000000 223092870
output:
2 29 999999971
result:
ok Correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
2 1000000000
output:
2 1 1
result:
ok Correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 4120kb
input:
649557664 933437700
output:
2 -7 649557671
result:
ok Correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 4156kb
input:
33396678 777360870
output:
2 1 33396677
result:
ok Correct
Test #7:
score: -100
Wrong Answer
time: 896ms
memory: 4116kb
input:
48205845 903124530
output:
3 -903124529 -903124499 1854454873
result:
wrong answer Integer element a[3] equals to 1854454873, violates the range [-10^9, 10^9]