QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#543300 | #9167. Coprime Array | code_side-effect | TL | 0ms | 3676kb | C++20 | 1.3kb | 2024-09-01 15:46:29 | 2024-09-01 15:46:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pi 3.14159265358979323846
#define int long long
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 200005;
void solve()
{
int s,x;
cin >> s >> x;
if(__gcd(s,x) == 1){
cout << 1 << "\n";
cout << s ;
return ;
}
if(s % 2 == 0){
cout << 2 << "\n";
}
else{
cout << 3 << "\n";
s--;
cout << 1 << " ";
}
int n = 0;
while(true){
if(__gcd(x, s-(n*x-1)) == 1){
cout << n*x-1 << " " << s-(n*x-1) << "\n";
return ;
}
if(__gcd(x, s-(n*x+1)) == 1){
cout << n*x+1 << " " << s-(n*x+1) << "\n";
return ;
}
int m = -1*n;
if(__gcd(x, s-(m*x-1)) == 1){
cout << m*x-1 << " " << s-(m*x-1) << "\n";
return ;
}
if(__gcd(x, s-(m*x+1)) == 1){
cout << m*x+1 << " " << s-(m*x+1) << "\n";
return ;
}
n++;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3676kb
input:
9 6
output:
3 1 1 7
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
14 34
output:
2 -1 15
result:
ok Correct
Test #3:
score: -100
Time Limit Exceeded
input:
1000000000 223092870