QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#512097 | #9167. Coprime Array | ucup-team1525# | AC ✓ | 1ms | 4064kb | C++20 | 1.4kb | 2024-08-10 13:30:50 | 2024-08-10 13:30:51 |
Judging History
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