{"problem":{"name":"[蓝桥杯 2024 国 A] gcd 与 lcm","description":{"content":"给定两个数 $x,y$，求有多少种不同的长度为 $n$ 的序列 $(a_1,a_2,\\cdots,a_n)$，其所有元素的最大公约数为 $x$ 且最小公倍数为 $y$。 两个序列 $(a_1,a_2,\\cdots,a_n)$ 与 $(b_1,b_2,\\cdots,b_n)$ 不同，是指存在至少一个位置 $i$ 满足 $a_i\\neq b_i$。 由于答案可能很大，请输出答案对 $998\\ 24","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10580"},"statements":[{"statement_type":"Markdown","content":"给定两个数 $x,y$，求有多少种不同的长度为 $n$ 的序列 $(a_1,a_2,\\cdots,a_n)$，其所有元素的最大公约数为 $x$ 且最小公倍数为 $y$。\n\n两个序列 $(a_1,a_2,\\cdots,a_n)$ 与 $(b_1,b_2,\\cdots,b_n)$ 不同，是指存在至少一个位置 $i$ 满足 $a_i\\neq b_i$。\n\n由于答案可能很大，请输出答案对 $998\\ 244\\ 353$ 取模后的结果。\n\n## Input\n\n输入的第一行包含一个整数 $Q$ 表示询问次数。\n\n接下来 $Q$ 行，每行包含三个整数 $x,y,n$ 表示一组询问，相邻整数之间使用一个空格分隔。对于每个询问，保证至少存在一个满足条件的序列。\n\n## Output\n\n输出 $Q$ 行，每行包含一个整数，依次表示每个询问的答案。\n\n[samples]\n\n## Note\n\n对于 $40\\%$ 的评测用例，$n\\le 30$；  \n对于 $70\\%$ 的评测用例，$n\\le 5000$；  \n对于所有评测用例，$1\\le Q\\le 100$，$2\\le n\\le 10^5$，$1\\le x,y\\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10580","tags":["2024","容斥原理","蓝桥杯国赛"],"sample_group":[["3\n3 6 2\n12 144 3\n233 251640 10","2\n72\n905954656"]],"created_at":"2026-03-03 11:09:25"}}