{"code":"2023usopenplatinum2","name":"USACO 2023 US Open Contest, Platinum, Good Bitstrings","description":"Với $2$ số nguyên dương $a$ và $b$ bất kì. Ta định nghĩa hàm ```gen_string(a, b)``` bởi đoạn code Python sau:\r\n```python\r\ndef gen_string(a: int, b: int):\r\n\tres = \"\"\r\n\tia, ib = 0, 0\r\n\twhile ia + ib < a + b:\r\n\t\tif ia * b <= ib * a:\r\n\t\t\tres += '0'\r\n\t\t\tia += 1\r\n\t\telse:\r\n\t\t\tres += '1'\r\n\t\t\tib += 1\r\n\treturn res\r\n```\r\n\r\nTương đương với đoạn code C++ sau:\r\n```cpp\r\nstring gen_string(int64_t a, int64_t b) {\r\n\tstring res;\r\n\tint ia = 0, ib = 0;\r\n\twhile (ia + ib < a + b) {\r\n\t\tif ((__int128)ia * b <= (__int128)ib * a) {\r\n\t\t\tres += '0';\r\n\t\t\tia++;\r\n\t\t} else {\r\n\t\t\tres += '1';\r\n\t\t\tib++;\r\n\t\t}\r\n\t}\r\n\treturn res;\r\n}\r\n```\r\n$ia$ sẽ bằng $a$ và $ib$ sẽ bằng $b$ khi vòng lặp kết thúc, như vậy hàm ```gen_string(a, b)``` trên sẽ sinh ra một xâu nhị phân độ dài $a + b$ chứa đúng $a$ bit $0$ và $b$ bit $1$. Ví dụ, ```gen_string(4,10)=01110110111011```.\r\n\r\nMột xâu nhị phân $s$ được gọi là \"tốt\" nếu như tồn tại $2$ số nguyên dương $x$ và $y$ sao cho $s =$ ```gen_string(x, y)```. Bạn được cho $2$ số $A$ và $B$ $(1 \\le A, B \\le 10^{18})$, bạn cần tính toán số xâu tiền tố \"tốt\" của xâu ```gen_string(A, B)```. Ví dụ, có $6$ xâu tiền tố \"tốt\" của xâu ```gen_string(4, 10)```:\r\n\r\n|    X    |    Y    |    gen_string(X, Y)            |\r\n|-------|--------|-----------------------------------|\r\n| x = 1 | y = 1  | gen_string(x, y) = 01             |\r\n| x = 1 | y = 2  | gen_string(x, y) = 011            |\r\n| x = 1 | y = 3  | gen_string(x, y) = 0111           |\r\n| x = 2 | y = 5  | gen_string(x, y) = 0111011        |\r\n| x = 3 | y = 7  | gen_string(x, y) = 0111011011     |\r\n| x = 4 | y = 10 | gen_string(x, y) = 01110110111011|\r\n\r\n#### Input\r\n- Dòng đầu tiên chứa số $T$ $(T \\le 10)$, chỉ số lượng test.\r\n- $T$ dòng tiếp theo, mỗi dòng chứa $2$ số $A$ và $B$.\r\n\r\n#### Output\r\n- Gồm $T$ dòng, mỗi dòng là đáp cho mỗi test.\r\n\r\n#### Scoring\r\n- Subtask $1$: $A, B \\le 100$.\r\n- Subtask $2$: $A, B \\le 1000$.\r\n- Subtask $3$: $A, B \\le 10^6$.\r\n- Subtask $4$: Không có quá $10^5$ xâu tiền tố tốt trong mỗi test.\r\n- Subtask $5$: Không có thêm ràng buộc.\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        6\r\n        1 1\r\n        3 5\r\n        4 7\r\n        8 20\r\n        4 10\r\n        27 21\r\n        ```\r\n    ???+ \"Output\"\r\n        ```sample\r\n        1\r\n        5\r\n        7\r\n        10\r\n        6\r\n        13\r\n        ```","points":1000.0,"partial":true,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}