#P12831. [蓝桥杯 2025 国 B] 互质藏卡
[蓝桥杯 2025 国 B] 互质藏卡
题目描述
小蓝整理着阁楼上的旧物,偶然发现了一个落满灰尘的卡片箱。打开箱子,里面整齐地摆放着 17600 张卡片,每张卡片上都写有一个数字,恰好包含了从 1 到 17600 的所有正整数。
儿时的他热衷于收集各种卡牌,数量之多令人咋舌。如今,再次翻阅这些尘封的记忆,小蓝不禁感慨万千。他想起收藏家前辈的箴言:“收藏的魅力在于精粹,而非数量”。于是,他决定从这些卡牌中选取 张,组成一套“互质藏卡”。
“互质藏卡”的特点在于:任意两张卡片上的数字之间互质,即它们的最大公约数恒为 。现在,请你帮小蓝计算,共有多少种不同的选取方案,使得选出的 张卡片满足“互质藏卡”的条件。由于答案可能很大,你只需给出其对 取余后的结果即可。
注意:两个选取方案被认为是不同的,当且仅当它们所包含的数字集合不完全相同。即,若存在至少一个数字出现在其中一个集合但不出现在另一个集合中,则这两个方案被视为不同。
输出格式
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。