{"problem":{"name":"[POI 2020/2021 R3] 收藏家 2 / Kolekcjoner Bajtemonów 2","description":{"content":"给你 $n$ 个数对，你要进行 $n$ 次二选一，这样你就有了 $n$ 个数，最大化这 $n$ 个数的 $\\gcd$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":600,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9401"},"statements":[{"statement_type":"Markdown","content":"给你 $n$ 个数对，你要进行 $n$ 次二选一，这样你就有了 $n$ 个数，最大化这 $n$ 个数的 $\\gcd$。\n\n## Input\n\n第一行一个正整数 $n$。\n\n接下来 $n$ 行，每行两个整数，$a_i,b_i$。\n\n## Output\n\n一行一个数：最大的 $\\gcd$。\n\n[samples]\n\n## Background\n\n译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Kolekcjoner Bajtemonów 2](https://szkopul.edu.pl/problemset/problem/yI8VISW680r7ktJAPvA5QPkl/statement/)。\n\n试机题。\n\n## Note\n\n对于所有数据，$1\\leq n\\leq 10^6$，$1\\leq a_i\\leq 5\\times 10^5$，$1\\leq b_i<2^{63}$。\n\n对于 $42pts$ 的数据，$n\\leq 5000$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9401","tags":["数学","2020","POI（波兰）","ST 表"],"sample_group":[["4\n5 7\n10 15\n13 20\n7 5\n","5"],["2\n18900 22050\n14700 17640\n","7350"],["见附件","2"]],"created_at":"2026-03-03 11:09:25"}}