QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#738409#9167. Coprime Arrayucup-team134#WA 896ms4156kbC++142.0kb2024-11-12 18:59:492024-11-12 18:59:50

Judging History

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

  • [2024-11-12 18:59:50]
  • 评测
  • 测评结果:WA
  • 用时:896ms
  • 内存:4156kb
  • [2024-11-12 18:59:49]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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]