QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#512097#9167. Coprime Arrayucup-team1525#AC ✓1ms4064kbC++201.4kb2024-08-10 13:30:502024-08-10 13:30:51

Judging History

你现在查看的是测评时间为 2024-08-10 13:30:51 的历史记录

  • [2024-10-14 07:51:52]
  • 管理员手动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1ms
  • 内存:4120kb
  • [2024-08-11 17:38:28]
  • hack成功,自动添加数据
  • (/hack/775)
  • [2024-08-10 13:30:51]
  • 评测
  • 测评结果:100
  • 用时:1ms
  • 内存:4064kb
  • [2024-08-10 13:30:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int s,x;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1; y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
pair<int,int> get(int a,int m1,int b,int m2){
    // if(m1==1) return make_pair(b,m2);
    int x,y;
    exgcd(m1,m2,x,y);
    x=(x%m2+m2)%m2;
    y=(y%m1+m1)%m1;
    // printf("%d %d\n",x,y);
    int M=m1*m2,V=(1ll*a*y*m2+1ll*b*x*m1)%M;
    return make_pair(V,M);
}
int crt(vector<int> &v,vector<int> &m){
    int V=0,M=1;
    for(int i=0;i<v.size();i++){
        // printf("v,m: %d %d\n",v[i],m[i]);
        auto [vv,mm]=get(V,M,v[i],m[i]);
        V=vv; M=mm;
        // printf("V,M: %d %d\n",V,M);
    }
    return V;
}
int main()
{
    scanf("%d%d",&s,&x);
    if (__gcd(s,x)==1)
    {
        printf("1\n%d",s);
        return 0;
    }
    int ox=x;
    vector<int> v,u;
    for (int i=2;i<=40000;++i)
        if (x%i==0)
        {
            v.push_back(i);
            while (x%i==0)
                x/=i;
        }
    if (x!=1)
        v.push_back(x);
    x=ox;
    if (s%2==1&&x%2==0)
    {
        printf("3\n");
        --s;
        printf("1 ");
    }
    else 
        printf("2\n");
    for (int z:v)
        if (s%z==1)
            u.push_back(2);
        else
            u.push_back(1);
    int o=crt(u,v);
    printf("%d %d\n",o,s-o);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3760kb

input:

9 6

output:

3
1 1 7

result:

ok Correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 4048kb

input:

14 34

output:

2
1 13

result:

ok Correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

1000000000 223092870

output:

2
148728581 851271419

result:

ok Correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

2 1000000000

output:

2
1 1

result:

ok Correct

Test #5:

score: 0
Accepted
time: 1ms
memory: 3768kb

input:

649557664 933437700

output:

2
83981 649473683

result:

ok Correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

33396678 777360870

output:

2
1 33396677

result:

ok Correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

48205845 903124530

output:

3
1 18811 48187033

result:

ok Correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

251037078 505905400

output:

2
1 251037077

result:

ok Correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

30022920 172746860

output:

2
1 30022919

result:

ok Correct

Test #10:

score: 0
Accepted
time: 0ms
memory: 4048kb

input:

63639298 808058790

output:

2
248711 63390587

result:

ok Correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

76579017 362768406

output:

3
1 1 76579015

result:

ok Correct

Test #12:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

40423669 121437778

output:

3
1 1 40423667

result:

ok Correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 4064kb

input:

449277309 720915195

output:

2
1 449277308

result:

ok Correct

Test #14:

score: 0
Accepted
time: 0ms
memory: 4052kb

input:

81665969 919836918

output:

3
1 68069 81597899

result:

ok Correct

Test #15:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

470578680 280387800

output:

2
1 470578679

result:

ok Correct

Test #16:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

58450340 803305503

output:

2
1 58450339

result:

ok Correct

Test #17:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

125896113 323676210

output:

3
1 59281 125836831

result:

ok Correct

Test #18:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

381905348 434752500

output:

2
1 381905347

result:

ok Correct

Test #19:

score: 0
Accepted
time: 0ms
memory: 4052kb

input:

78916498 653897673

output:

1
78916498

result:

ok Correct

Test #20:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

35787885 270845190

output:

3
1 1 35787883

result:

ok Correct

Extra Test:

score: 0
Extra Test Passed