#include using namespace std; #define rep(i, n) for(int i=0; i #include //vectorの中身を空白区切りで出力 template void print1(vector v) { for (int i = 0; i < v.size(); i++) { cout << v[i]; if (i < v.size() - 1) { cout << " "; } } } //vectorの中身を改行区切りで出力 template void print2(vector v) { for (auto x : v) { cout << x << endl; } } //二次元配列を出力 template void printvv(vector> vv) { for (vector v : vv) { print1(v); cout << endl; } } //vectorを降順にソート template void rsort(vector &v) { sort(v.begin(), v.end()); reverse(v.begin(), v.end()); } //昇順priority_queueを召喚 template struct rpriority_queue { priority_queue, greater> pq; void push(T x) { pq.push(x); } void pop() { pq.pop(); } T top() { return pq.top(); } size_t size() { return pq.size(); } bool empty() { return pq.empty(); } }; //高速10^n計算(mod mod) ll tenth(int n) { if (n == 0) { return 1; } else if (n % 2 == 0) { ll x = tenth(n / 2); x %= mod; x *= x; x %= mod; return x; } else { ll x = tenth(n - 1); x *= 10; x %= mod; return x; } } //高速a^n計算 ll power(int a, int n){ if(n == 0){ return 1; } else if(n % 2 == 0){ ll x = power(a, n / 2); x *= x; return x; } else { ll x = power(a, n - 1); x *= a; return x; } } //n以下の素数列を生成 vector prime (int n) { vector ch(n, false); vector pr; for(int i = 2; i <= n; i++){ if(!ch[i]){ pr.push_back(i); for(int j = 1; i*j<=n; j++){ ch[i*j]=true; } } } return pr; } //最大公約数(ユークリッドの互除法) ll gcd (ll a, ll b){ if(b>a){ swap(a, b); } while(a%b!=0){ ll t = a; a = b; b = t%b; } return b; } //最小公倍数(gcdを定義しておく) ll lcm (ll a, ll b){ ll g = gcd(a, b); ll x = (a/g)*b; return x; } //角XYZ(偏角Z→X)の角度([0,2π)) double angle(vector X, vector Y, vectorZ) { vector x = { X[0] - Y[0],X[1] - Y[1] }; vector z = { Z[0] - Y[0],Z[1] - Y[1] }; double pre, post; pre = atan2(x[1], x[0]); post = atan2(z[1], z[0]); if (post < 0) { post += pi*2; } if (pre < 0) { pre += pi*2; } if (pre < post) { pre += pi * 2; } return pre - post; } //mod mod下で逆元を算出する //高速a^n計算(mod ver.) ll mypower(ll a, ll n, ll Mod=mod) { if (n == 0) { return 1; } else if (n % 2 == 0) { ll x = mypower(a, n / 2,Mod); x *= x; x %= Mod; return x; } else { ll x = mypower(a, n - 1,Mod); x *= a; x %= Mod; return x; } } //フェルマーの小定理を利用 ll modinv(ll p, ll Mod=mod) { return mypower(p, Mod - 2,Mod) % Mod; } ////素因数分解(osa_k法)(前計算O(N)、素数判定O(1)、素因数分解(O(logN)) //エラトステネスの篩の代わりとしても使える(N項のvectorを生成するため、巨大数に対しては√Nまでの素数リストを作って割る方が良い) struct osa_k { //最大値までの各自然数に対し、その最小の素因数を格納するリスト vector min_prime_list; int upper_limit; osa_k(int N) { //N:最大値。一つの自然数の素因数分解にしか興味が泣ければそれを入力 vector v(N + 1); upper_limit = N; rep(i, N + 1) { v[i] = i; } swap(min_prime_list, v); //k=2から見る for (int k = 2; k * k <= N; k++) { if (min_prime_list[k] == k) { //最小の素因数=自分ならば、素数 //kが素数の時、t=k*kから始めてt=Nまでのkの倍数全てを確認する。未更新の自然数があれば、それの最小の素因数をkに更新する。 //k*k未満のkの倍数に対しては、kが最小の素因数にはなり得ないので計算する必要が無い for (int t = k * k; t <= N; t += k) { if (min_prime_list[t] == t) { min_prime_list[t] = k; } } } } } //任意の自然数nが素数であればtrueを返す bool isPrime(int n) { if (n < 2) { return false; } else { return min_prime_list[n] == n; } } //任意の自然数nの素因数分解を行う。素因数はvectorで与えられる(ex:n=12 -> {2,2,3}) vector devPrimes(int n) { vector vec; int now = n; while (now > 1) { vec.push_back(min_prime_list[now]); now /= min_prime_list[now]; } return vec; } }; //最大流問題を解く構造体(Ford-Fulkerson法.O(FE)) struct maxflow { struct Edge { int to, rev; ll capacity, init_capacity; int off, on; Edge(int _to, int _rev, ll _capacity, int _off, int _on) :to(_to), rev(_rev), capacity(_capacity), init_capacity(_capacity), off(_off), on(_on) {}; }; int delay=0; vector> Graph; maxflow(int MAX_V, int d) { Graph.assign(MAX_V, {}); delay=d; } void input(int from, int to, ll capacity, int off, int on) { int e_id = Graph[from].size(); int r_id = Graph[to].size(); Graph[from].push_back(Edge(to, r_id, capacity, off, on)); Graph[to].push_back(Edge(from, e_id, 0, on+delay, off-delay)); } Edge& rev_Edge(Edge& edge) { return Graph[edge.to][edge.rev]; } vector visited; ll dfs(int now, int g, ll flow, int time) { visited[now] = true; if (now == g) { return flow; } else { ll f = 0; ll res_flow = flow; for (Edge& edge : Graph[now]) { if (!visited[edge.to] && edge.capacity > 0 && edge.off>=time && edge.on<=1e9) { ll f_delta = dfs(edge.to, g, min(res_flow, edge.capacity), edge.on+delay); edge.capacity -= f_delta; rev_Edge(edge).capacity += f_delta; f += f_delta; res_flow -= f_delta; if (res_flow == 0) { break; } } } return f; } } void flowing(int s, int g, ll init_flow = INF) { bool cont = true; while (cont) { visited.assign(Graph.size(), false); ll flow = dfs(s, g, init_flow,0); init_flow -= flow; if (flow == 0) { cont = false; } } } ll get_flow(int g) { ll flow = 0; for (Edge& edge : Graph[g]) { Edge& rev_edge = rev_Edge(edge); ll tmp_flow = rev_edge.init_capacity - rev_edge.capacity; if (tmp_flow > 0) { flow += tmp_flow; } } return flow; } vector> flowing_edges() { vector> vec; rep(from, Graph.size()) { for (Edge& edge : Graph[from]) { ll flow = edge.init_capacity - edge.capacity; if (flow > 0) { vec.push_back({ from,edge.to,flow }); } } } return vec; } }; //Dinic法でのmax-flow。最大マッチングなど辺のキャパシティが小さい場合には高速 struct Dinic { struct Edge { int to, rev; ll capacity, init_capacity; ld cost; Edge(int _to, int _rev, ll _capacity,ld _cost) :to(_to), rev(_rev), capacity(_capacity),init_capacity(_capacity),cost(_cost) {}; }; vector> Graph; Edge& rev_Edge(Edge& edge) { return Graph[edge.to][edge.rev]; } vector level,itr; Dinic(int MAX_V) { Graph.assign(MAX_V, {}); } void input(int _from, int _to, ll _capacity,ld _cost) { int e_id = Graph[_from].size(), r_id = Graph[_to].size(); Graph[_from].push_back(Edge(_to, r_id, _capacity,_cost)); Graph[_to].push_back(Edge(_from, e_id, 0LL,_cost)); } void bfs(int s, int g, ld val) { level.assign(Graph.size(), -1); level[s] = 0; queue q; q.push(s); while (!q.empty()) { int now = q.front(); q.pop(); if (now == g) { continue; } for (Edge &e : Graph[now]) { if (level[e.to] == -1 && e.capacity > 0 && e.cost<=val) { level[e.to] = level[now] + 1; q.push(e.to); } } } } ll dfs(int now, int g, ll flow, ld val) { if (now == g) { return flow; } else if (level[now] >= level[g]) { return 0; //gよりも深い場所に行こうとしたら終わり。flow=0を返す } else { ll res_flow = flow; ll f = 0; for (int &i = itr[now]; i < Graph[now].size(); i++) { Edge& edge = Graph[now][i]; if (level[edge.to] == level[now] + 1 && edge.capacity > 0 && edge.cost<=val) { ll f_delta = dfs(edge.to, g, min(res_flow, edge.capacity), val); edge.capacity -= f_delta; rev_Edge(edge).capacity += f_delta; res_flow -= f_delta; f += f_delta; if (res_flow == 0) { break; } } } return f; //行先が無い場合はflow=0を返す } } void flowing(int s, int g, ll init_flow = INF, ld val=0) { bool cont1 = true; while (cont1) { bfs(s, g,val); if (level[g] == -1) { cont1 = false; } else { bool cont2 = true; while (cont2) { itr.assign(Graph.size(), 0); ll flow = dfs(s, g, init_flow,val); init_flow -= flow; if (flow == 0) { cont2 = false; } } } if(init_flow==0){ cont1=false; } } } ll get_flow(int g) { ll flow = 0; for (Edge& edge : Graph[g]) { flow += max(0LL, rev_Edge(edge).init_capacity - rev_Edge(edge).capacity); } return flow; } vector> flowing_edges(){ vector> vec; for (int from = 0; from < Graph.size(); from++) { for (Edge& edge : Graph[from]) { if (edge.init_capacity - edge.capacity > 0) { vec.push_back({ from,edge.to,edge.init_capacity - edge.capacity }); } } } return vec; } void reset() { for (int from = 0; from < Graph.size(); from++) { for (Edge& edge : Graph[from]) { edge.capacity = edge.init_capacity; } } } }; struct SegTree{ vector tree; int n=1; SegTree(int N){ while(n0){ update((now-1)/2); } } void add(int i, int d){ tree[n-1+i]+=d; update((n-2+i)/2); } int sum(int l, int r, int b, int u, int now){ if(r<=b || l>=u){ return 0; } else if(l<=b && r>=u){ return tree[now]; } else{ return sum(l,r,b,(b+u)/2,now*2+1)+sum(l,r,(b+u)/2,u,now*2+2); } } int query(int L, int R){ return sum(L,R+1,0,n,0); } }; int main(){ ll P,Q; cin>>P>>Q; ll g=gcd(P,Q); ll p=P/g, q=Q/g; if(p>q*2){ cout<<0<> s; ll k=1; { ll l=0, r=1e9+5; while(r>l+1){ ll mid=(l+r)/2; if(sqrt(ld(mid*q))*2<=mid*p){ r=mid; } else{ l=mid; } } k=r; } ll x=floor(sqrt(k*q)); while(x>=1){ ld py=k*p-x, qy=ld(k*q)/ld(x); if(qyl+1){ ll mid=(l+r)/2; if(ld(mid*q)/ld(x) < mid*p-x){ l=mid; } else{ r=mid; } } k=r; py=k*p-x, qy=ld(k*q)/ld(x); } if(py==qy){ s.insert({x,ll(py)}); s.insert({ll(py),x}); } x--; } cout< v:s){ cout<