QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#722656 | #9167. Coprime Array | Kangliyang | AC ✓ | 0ms | 3940kb | C++14 | 1.4kb | 2024-11-07 19:49:34 | 2024-11-07 19:49:35 |
Judging History
answer
#include <bits/stdc++.h>
#define in(x) freopen(#x".in","r",stdin)
#define out(x) freopen(#x".out","w",stdout)
#define make(x) freopen(#x".in","w",stdout)
#define ll long long
#define int long long
#ifdef MY_COMPUTER
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
#define vector basic_string
#define pii array<int,2>
using namespace std;
inline int read()
{
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
template<typename _it>
void read(_it a,_it b){
while(a!=b) (*a)=read(),a++;
}
template<typename _it>
void write(const char* form,_it a,_it b,int op=0){
while(a!=b) printf(form,*a),a++;
if(op) puts("");
}
int s,x;
int gcd(int a,int b){
a=llabs(a),b=llabs(b);
if(!a) return b;
return !b?a:gcd(b,a%b);
}
signed main(){
s=read(),x=read();
if(gcd(s,x)==1){
puts("1");
printf("%lld\n",s);
return 0;
}
if(s%2==1&&x%2==0){
for(int i=(x/3+2)/2*2+1;;i+=2){
if(gcd(i,x)==1&&gcd((s-i)/2,x)==1){
puts("3");
printf("%lld %lld %lld\n",(s-i)/2,(s-i)/2,i);
return 0;
}
}
}
else{
for(int i=(s+1)/2;;i++){
if(gcd(i,x)==1&&gcd(s-i,x)==1){
puts("2");
printf("%lld %lld\n",i,s-i);
return 0;
}
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3872kb
input:
9 6
output:
3 1 1 7
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
14 34
output:
2 7 7
result:
ok Correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
1000000000 223092870
output:
2 500000021 499999979
result:
ok Correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
2 1000000000
output:
2 1 1
result:
ok Correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
649557664 933437700
output:
2 324778841 324778823
result:
ok Correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
33396678 777360870
output:
2 16698349 16698329
result:
ok Correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
48205845 903124530
output:
3 -126417839 -126417839 301041523
result:
ok Correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
251037078 505905400
output:
2 125518539 125518539
result:
ok Correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
30022920 172746860
output:
2 15011467 15011453
result:
ok Correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
63639298 808058790
output:
2 31819649 31819649
result:
ok Correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
76579017 362768406
output:
3 -22171895 -22171895 120922807
result:
ok Correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
40423669 121437778
output:
3 -27799 -27799 40479267
result:
ok Correct
Test #13:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
449277309 720915195
output:
2 224638658 224638651
result:
ok Correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
81665969 919836918
output:
3 -112473181 -112473181 306612331
result:
ok Correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
470578680 280387800
output:
2 235289357 235289323
result:
ok Correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
58450340 803305503
output:
2 29225176 29225164
result:
ok Correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
125896113 323676210
output:
3 9002017 9002017 107892079
result:
ok Correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
381905348 434752500
output:
2 190952689 190952659
result:
ok Correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
78916498 653897673
output:
1 78916498
result:
ok Correct
Test #20:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
35787885 270845190
output:
3 -27246929 -27246929 90281743
result:
ok Correct
Extra Test:
score: 0
Extra Test Passed