QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#738435 | #9167. Coprime Array | ucup-team134# | TL | 0ms | 3924kb | C++14 | 2.0kb | 2024-11-12 19:03:40 | 2024-11-12 19:03:41 |
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<=max(s,x);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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3856kb
input:
9 6
output:
3 -5 -5 19
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
14 34
output:
2 1 13
result:
ok Correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
1000000000 223092870
output:
2 29 999999971
result:
ok Correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
2 1000000000
output:
2 1 1
result:
ok Correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
649557664 933437700
output:
2 -7 649557671
result:
ok Correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
33396678 777360870
output:
2 1 33396677
result:
ok Correct
Test #7:
score: -100
Time Limit Exceeded
input:
48205845 903124530