#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC opimize(-O3)
//#pragma GCC opimize(Ofast)
//#pragma GCC opimize(unroll-loops)
//#pragma GCC target("avx,avx2,popcnt,sse,sse2,sse3,sse4,abm,tune=native")
#define m_p make_pair
#define vec vector
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef pair<int,int> pii;
const int N=4e5+1;
int ok=1;
int used[N];
vec<int>g[N];
int pref[N];
vec<int>ord;
void dfs(int v){
used[v]=1;
for(auto &z : g[v]){
if(used[z]==1){
ok=0;
}
else if(!used[z]){
dfs(z);
}
}
used[v]=2;
}
void dfs1(int v){
used[v]=1;
for(auto &z : g[v]){
if(!used[z]){
dfs1(z);
}
}
ord.pb(v);
}
int getlen(int n,int m){
return n+m-__gcd(n,m)-1;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int q=10;
scanf("%d",&q);
// cin>>q;
// ofstream cout("out.txt");
while(q--){
int n,m;
// n=199999;m=200000;
ord.clear();
scanf("%d%d",&n,&m);
int wow=getlen(n,m);
auto check=[&](int mid){
for(int i=0;i<=mid;i++) g[i].clear(),used[i]=0;
for(int i=0;i<=mid;i++){
if(i>=n){
g[i-n].pb(i);
}
if(i>=m){
g[i].pb(i-m);
}
}
ok=1;
for(int i=0;i<=mid;i++){
if(!used[i]){
dfs(i);
}
}
return ok;
};
int l=0,r=n+m;
while(l!=r){
int tm=(l+r)>>1;
if(check(tm)){
l=tm+1;
}
else{
r=tm;
}
}
l--;
assert(l==wow);
for(int i=0;i<=l;i++) g[i].clear(),used[i]=0;
for(int i=0;i<=l;i++){
if(i>=n){
g[i-n].pb(i);
}
if(i>=m){
g[i].pb(i-m);
}
}
for(int i=0;i<=l;i++){
if(!used[i]){
dfs1(i);
}
}
// reverse(all(ord));
int i=1;
for(auto &z : ord) pref[z]=i++;
// cout<<l<<'\n';
printf("%d%c",l,'\n');
// cout<<l<<'\n';
for(int i=1;i<=l;i++){
// cout<<pref[i]-pref[i-1]<<' ';
printf("%d%c",pref[i]-pref[i-1],' ');
}
printf("%c",'\n');
// cout<<'\n';
}
return 0;
}
/*
5 1
1 1 2
1 3 5
3 2 3 1
2 1
3 0 3 1
*/
Compilation message
sequence.cpp: In function 'int main()':
sequence.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
sequence.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%d%d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Ok |
2 |
Correct |
6 ms |
9676 KB |
Ok |
3 |
Correct |
7 ms |
9676 KB |
Ok |
4 |
Correct |
6 ms |
9676 KB |
Ok |
5 |
Correct |
6 ms |
9676 KB |
Ok |
6 |
Correct |
6 ms |
9732 KB |
Ok |
7 |
Correct |
6 ms |
9676 KB |
Ok |
8 |
Correct |
6 ms |
9676 KB |
Ok |
9 |
Correct |
6 ms |
9676 KB |
Ok |
10 |
Correct |
6 ms |
9676 KB |
Ok |
11 |
Correct |
6 ms |
9676 KB |
Ok |
12 |
Correct |
6 ms |
9676 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9616 KB |
Ok |
2 |
Correct |
6 ms |
9676 KB |
Ok |
3 |
Correct |
6 ms |
9676 KB |
Ok |
4 |
Correct |
7 ms |
9676 KB |
Ok |
5 |
Correct |
7 ms |
9676 KB |
Ok |
6 |
Correct |
12 ms |
9936 KB |
Ok |
7 |
Correct |
37 ms |
10908 KB |
Ok |
8 |
Correct |
19 ms |
10264 KB |
Ok |
9 |
Correct |
41 ms |
11032 KB |
Ok |
10 |
Correct |
25 ms |
10512 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Ok |
2 |
Correct |
6 ms |
9676 KB |
Ok |
3 |
Correct |
23 ms |
9676 KB |
Ok |
4 |
Correct |
7 ms |
9720 KB |
Ok |
5 |
Correct |
6 ms |
9676 KB |
Ok |
6 |
Correct |
13 ms |
9676 KB |
Ok |
7 |
Correct |
6 ms |
9676 KB |
Ok |
8 |
Correct |
6 ms |
9664 KB |
Ok |
9 |
Correct |
6 ms |
9676 KB |
Ok |
10 |
Correct |
5 ms |
9676 KB |
Ok |
11 |
Correct |
6 ms |
9676 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Ok |
2 |
Correct |
6 ms |
9676 KB |
Ok |
3 |
Correct |
6 ms |
9640 KB |
Ok |
4 |
Correct |
7 ms |
9676 KB |
Ok |
5 |
Correct |
6 ms |
9676 KB |
Ok |
6 |
Correct |
488 ms |
27528 KB |
Ok |
7 |
Correct |
417 ms |
29500 KB |
Ok |
8 |
Correct |
929 ms |
32228 KB |
Ok |
9 |
Correct |
534 ms |
29472 KB |
Ok |
10 |
Correct |
262 ms |
20704 KB |
Ok |
11 |
Correct |
444 ms |
30904 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Ok |
2 |
Correct |
6 ms |
9676 KB |
Ok |
3 |
Correct |
7 ms |
9676 KB |
Ok |
4 |
Correct |
6 ms |
9676 KB |
Ok |
5 |
Correct |
6 ms |
9676 KB |
Ok |
6 |
Correct |
6 ms |
9732 KB |
Ok |
7 |
Correct |
6 ms |
9676 KB |
Ok |
8 |
Correct |
6 ms |
9676 KB |
Ok |
9 |
Correct |
6 ms |
9676 KB |
Ok |
10 |
Correct |
6 ms |
9676 KB |
Ok |
11 |
Correct |
6 ms |
9676 KB |
Ok |
12 |
Correct |
6 ms |
9676 KB |
Ok |
13 |
Correct |
6 ms |
9676 KB |
Ok |
14 |
Correct |
6 ms |
9676 KB |
Ok |
15 |
Correct |
23 ms |
9676 KB |
Ok |
16 |
Correct |
7 ms |
9720 KB |
Ok |
17 |
Correct |
6 ms |
9676 KB |
Ok |
18 |
Correct |
13 ms |
9676 KB |
Ok |
19 |
Correct |
6 ms |
9676 KB |
Ok |
20 |
Correct |
6 ms |
9664 KB |
Ok |
21 |
Correct |
6 ms |
9676 KB |
Ok |
22 |
Correct |
5 ms |
9676 KB |
Ok |
23 |
Correct |
6 ms |
9676 KB |
Ok |
24 |
Correct |
11 ms |
9804 KB |
Ok |
25 |
Correct |
11 ms |
9804 KB |
Ok |
26 |
Correct |
11 ms |
9872 KB |
Ok |
27 |
Correct |
11 ms |
9816 KB |
Ok |
28 |
Correct |
10 ms |
9804 KB |
Ok |
29 |
Correct |
10 ms |
9804 KB |
Ok |
30 |
Correct |
38 ms |
9756 KB |
Ok |
31 |
Correct |
11 ms |
9804 KB |
Ok |
32 |
Correct |
11 ms |
9888 KB |
Ok |
33 |
Correct |
10 ms |
9868 KB |
Ok |
34 |
Correct |
19 ms |
10188 KB |
Ok |
35 |
Correct |
18 ms |
10120 KB |
Ok |
36 |
Correct |
18 ms |
10188 KB |
Ok |
37 |
Correct |
18 ms |
10124 KB |
Ok |
38 |
Correct |
17 ms |
10172 KB |
Ok |
39 |
Correct |
20 ms |
10148 KB |
Ok |
40 |
Correct |
19 ms |
10168 KB |
Ok |
41 |
Correct |
18 ms |
10188 KB |
Ok |
42 |
Correct |
20 ms |
10152 KB |
Ok |
43 |
Correct |
19 ms |
10196 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Ok |
2 |
Correct |
6 ms |
9676 KB |
Ok |
3 |
Correct |
7 ms |
9676 KB |
Ok |
4 |
Correct |
6 ms |
9676 KB |
Ok |
5 |
Correct |
6 ms |
9676 KB |
Ok |
6 |
Correct |
6 ms |
9732 KB |
Ok |
7 |
Correct |
6 ms |
9676 KB |
Ok |
8 |
Correct |
6 ms |
9676 KB |
Ok |
9 |
Correct |
6 ms |
9676 KB |
Ok |
10 |
Correct |
6 ms |
9676 KB |
Ok |
11 |
Correct |
6 ms |
9676 KB |
Ok |
12 |
Correct |
6 ms |
9676 KB |
Ok |
13 |
Correct |
6 ms |
9616 KB |
Ok |
14 |
Correct |
6 ms |
9676 KB |
Ok |
15 |
Correct |
6 ms |
9676 KB |
Ok |
16 |
Correct |
7 ms |
9676 KB |
Ok |
17 |
Correct |
7 ms |
9676 KB |
Ok |
18 |
Correct |
12 ms |
9936 KB |
Ok |
19 |
Correct |
37 ms |
10908 KB |
Ok |
20 |
Correct |
19 ms |
10264 KB |
Ok |
21 |
Correct |
41 ms |
11032 KB |
Ok |
22 |
Correct |
25 ms |
10512 KB |
Ok |
23 |
Correct |
6 ms |
9676 KB |
Ok |
24 |
Correct |
6 ms |
9676 KB |
Ok |
25 |
Correct |
23 ms |
9676 KB |
Ok |
26 |
Correct |
7 ms |
9720 KB |
Ok |
27 |
Correct |
6 ms |
9676 KB |
Ok |
28 |
Correct |
13 ms |
9676 KB |
Ok |
29 |
Correct |
6 ms |
9676 KB |
Ok |
30 |
Correct |
6 ms |
9664 KB |
Ok |
31 |
Correct |
6 ms |
9676 KB |
Ok |
32 |
Correct |
5 ms |
9676 KB |
Ok |
33 |
Correct |
6 ms |
9676 KB |
Ok |
34 |
Correct |
11 ms |
9804 KB |
Ok |
35 |
Correct |
11 ms |
9804 KB |
Ok |
36 |
Correct |
11 ms |
9872 KB |
Ok |
37 |
Correct |
11 ms |
9816 KB |
Ok |
38 |
Correct |
10 ms |
9804 KB |
Ok |
39 |
Correct |
10 ms |
9804 KB |
Ok |
40 |
Correct |
38 ms |
9756 KB |
Ok |
41 |
Correct |
11 ms |
9804 KB |
Ok |
42 |
Correct |
11 ms |
9888 KB |
Ok |
43 |
Correct |
10 ms |
9868 KB |
Ok |
44 |
Correct |
19 ms |
10188 KB |
Ok |
45 |
Correct |
18 ms |
10120 KB |
Ok |
46 |
Correct |
18 ms |
10188 KB |
Ok |
47 |
Correct |
18 ms |
10124 KB |
Ok |
48 |
Correct |
17 ms |
10172 KB |
Ok |
49 |
Correct |
20 ms |
10148 KB |
Ok |
50 |
Correct |
19 ms |
10168 KB |
Ok |
51 |
Correct |
18 ms |
10188 KB |
Ok |
52 |
Correct |
20 ms |
10152 KB |
Ok |
53 |
Correct |
19 ms |
10196 KB |
Ok |
54 |
Correct |
300 ms |
15312 KB |
Ok |
55 |
Correct |
379 ms |
15560 KB |
Ok |
56 |
Correct |
374 ms |
15716 KB |
Ok |
57 |
Correct |
222 ms |
14684 KB |
Ok |
58 |
Correct |
288 ms |
15116 KB |
Ok |
59 |
Correct |
245 ms |
14784 KB |
Ok |
60 |
Correct |
218 ms |
14388 KB |
Ok |
61 |
Correct |
242 ms |
14916 KB |
Ok |
62 |
Correct |
330 ms |
15460 KB |
Ok |
63 |
Correct |
245 ms |
14724 KB |
Ok |
64 |
Correct |
340 ms |
15584 KB |
Ok |
65 |
Correct |
295 ms |
15288 KB |
Ok |
66 |
Correct |
269 ms |
15128 KB |
Ok |
67 |
Correct |
229 ms |
14888 KB |
Ok |
68 |
Correct |
274 ms |
15164 KB |
Ok |
69 |
Correct |
981 ms |
24696 KB |
Ok |
70 |
Correct |
1157 ms |
25348 KB |
Ok |
71 |
Correct |
1000 ms |
24828 KB |
Ok |
72 |
Correct |
962 ms |
24748 KB |
Ok |
73 |
Correct |
1006 ms |
24760 KB |
Ok |
74 |
Correct |
1140 ms |
24668 KB |
Ok |
75 |
Correct |
1081 ms |
24408 KB |
Ok |
76 |
Correct |
1099 ms |
24984 KB |
Ok |
77 |
Correct |
984 ms |
24228 KB |
Ok |
78 |
Correct |
878 ms |
24888 KB |
Ok |
79 |
Correct |
932 ms |
25032 KB |
Ok |
80 |
Correct |
969 ms |
25200 KB |
Ok |
81 |
Correct |
1146 ms |
24856 KB |
Ok |
82 |
Correct |
964 ms |
24964 KB |
Ok |
83 |
Correct |
939 ms |
24500 KB |
Ok |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Ok |
2 |
Correct |
6 ms |
9676 KB |
Ok |
3 |
Correct |
7 ms |
9676 KB |
Ok |
4 |
Correct |
6 ms |
9676 KB |
Ok |
5 |
Correct |
6 ms |
9676 KB |
Ok |
6 |
Correct |
6 ms |
9732 KB |
Ok |
7 |
Correct |
6 ms |
9676 KB |
Ok |
8 |
Correct |
6 ms |
9676 KB |
Ok |
9 |
Correct |
6 ms |
9676 KB |
Ok |
10 |
Correct |
6 ms |
9676 KB |
Ok |
11 |
Correct |
6 ms |
9676 KB |
Ok |
12 |
Correct |
6 ms |
9676 KB |
Ok |
13 |
Correct |
6 ms |
9616 KB |
Ok |
14 |
Correct |
6 ms |
9676 KB |
Ok |
15 |
Correct |
6 ms |
9676 KB |
Ok |
16 |
Correct |
7 ms |
9676 KB |
Ok |
17 |
Correct |
7 ms |
9676 KB |
Ok |
18 |
Correct |
12 ms |
9936 KB |
Ok |
19 |
Correct |
37 ms |
10908 KB |
Ok |
20 |
Correct |
19 ms |
10264 KB |
Ok |
21 |
Correct |
41 ms |
11032 KB |
Ok |
22 |
Correct |
25 ms |
10512 KB |
Ok |
23 |
Correct |
6 ms |
9676 KB |
Ok |
24 |
Correct |
6 ms |
9676 KB |
Ok |
25 |
Correct |
23 ms |
9676 KB |
Ok |
26 |
Correct |
7 ms |
9720 KB |
Ok |
27 |
Correct |
6 ms |
9676 KB |
Ok |
28 |
Correct |
13 ms |
9676 KB |
Ok |
29 |
Correct |
6 ms |
9676 KB |
Ok |
30 |
Correct |
6 ms |
9664 KB |
Ok |
31 |
Correct |
6 ms |
9676 KB |
Ok |
32 |
Correct |
5 ms |
9676 KB |
Ok |
33 |
Correct |
6 ms |
9676 KB |
Ok |
34 |
Correct |
6 ms |
9676 KB |
Ok |
35 |
Correct |
6 ms |
9676 KB |
Ok |
36 |
Correct |
6 ms |
9640 KB |
Ok |
37 |
Correct |
7 ms |
9676 KB |
Ok |
38 |
Correct |
6 ms |
9676 KB |
Ok |
39 |
Correct |
488 ms |
27528 KB |
Ok |
40 |
Correct |
417 ms |
29500 KB |
Ok |
41 |
Correct |
929 ms |
32228 KB |
Ok |
42 |
Correct |
534 ms |
29472 KB |
Ok |
43 |
Correct |
262 ms |
20704 KB |
Ok |
44 |
Correct |
444 ms |
30904 KB |
Ok |
45 |
Correct |
11 ms |
9804 KB |
Ok |
46 |
Correct |
11 ms |
9804 KB |
Ok |
47 |
Correct |
11 ms |
9872 KB |
Ok |
48 |
Correct |
11 ms |
9816 KB |
Ok |
49 |
Correct |
10 ms |
9804 KB |
Ok |
50 |
Correct |
10 ms |
9804 KB |
Ok |
51 |
Correct |
38 ms |
9756 KB |
Ok |
52 |
Correct |
11 ms |
9804 KB |
Ok |
53 |
Correct |
11 ms |
9888 KB |
Ok |
54 |
Correct |
10 ms |
9868 KB |
Ok |
55 |
Correct |
19 ms |
10188 KB |
Ok |
56 |
Correct |
18 ms |
10120 KB |
Ok |
57 |
Correct |
18 ms |
10188 KB |
Ok |
58 |
Correct |
18 ms |
10124 KB |
Ok |
59 |
Correct |
17 ms |
10172 KB |
Ok |
60 |
Correct |
20 ms |
10148 KB |
Ok |
61 |
Correct |
19 ms |
10168 KB |
Ok |
62 |
Correct |
18 ms |
10188 KB |
Ok |
63 |
Correct |
20 ms |
10152 KB |
Ok |
64 |
Correct |
19 ms |
10196 KB |
Ok |
65 |
Correct |
300 ms |
15312 KB |
Ok |
66 |
Correct |
379 ms |
15560 KB |
Ok |
67 |
Correct |
374 ms |
15716 KB |
Ok |
68 |
Correct |
222 ms |
14684 KB |
Ok |
69 |
Correct |
288 ms |
15116 KB |
Ok |
70 |
Correct |
245 ms |
14784 KB |
Ok |
71 |
Correct |
218 ms |
14388 KB |
Ok |
72 |
Correct |
242 ms |
14916 KB |
Ok |
73 |
Correct |
330 ms |
15460 KB |
Ok |
74 |
Correct |
245 ms |
14724 KB |
Ok |
75 |
Correct |
340 ms |
15584 KB |
Ok |
76 |
Correct |
295 ms |
15288 KB |
Ok |
77 |
Correct |
269 ms |
15128 KB |
Ok |
78 |
Correct |
229 ms |
14888 KB |
Ok |
79 |
Correct |
274 ms |
15164 KB |
Ok |
80 |
Correct |
981 ms |
24696 KB |
Ok |
81 |
Correct |
1157 ms |
25348 KB |
Ok |
82 |
Correct |
1000 ms |
24828 KB |
Ok |
83 |
Correct |
962 ms |
24748 KB |
Ok |
84 |
Correct |
1006 ms |
24760 KB |
Ok |
85 |
Correct |
1140 ms |
24668 KB |
Ok |
86 |
Correct |
1081 ms |
24408 KB |
Ok |
87 |
Correct |
1099 ms |
24984 KB |
Ok |
88 |
Correct |
984 ms |
24228 KB |
Ok |
89 |
Correct |
878 ms |
24888 KB |
Ok |
90 |
Correct |
932 ms |
25032 KB |
Ok |
91 |
Correct |
969 ms |
25200 KB |
Ok |
92 |
Correct |
1146 ms |
24856 KB |
Ok |
93 |
Correct |
964 ms |
24964 KB |
Ok |
94 |
Correct |
939 ms |
24500 KB |
Ok |
95 |
Correct |
944 ms |
24456 KB |
Ok |
96 |
Correct |
1500 ms |
30896 KB |
Ok |
97 |
Correct |
1172 ms |
27152 KB |
Ok |
98 |
Correct |
771 ms |
27108 KB |
Ok |
99 |
Correct |
1119 ms |
26680 KB |
Ok |
100 |
Correct |
1080 ms |
26180 KB |
Ok |
101 |
Correct |
1059 ms |
29064 KB |
Ok |
102 |
Correct |
1125 ms |
27188 KB |
Ok |
103 |
Correct |
1034 ms |
28284 KB |
Ok |
104 |
Correct |
1440 ms |
30016 KB |
Ok |
105 |
Correct |
1395 ms |
30424 KB |
Ok |
106 |
Correct |
1254 ms |
30568 KB |
Ok |
107 |
Correct |
1137 ms |
29540 KB |
Ok |
108 |
Correct |
1724 ms |
30368 KB |
Ok |
109 |
Correct |
1590 ms |
31620 KB |
Ok |
110 |
Execution timed out |
2083 ms |
40944 KB |
Time limit exceeded |
111 |
Halted |
0 ms |
0 KB |
- |