#P12831. [蓝桥杯 2025 国 B] 互质藏卡

    ID: 12607 Type: RemoteJudge 1000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 3 Uploaded By: Tags>2025数论素数判断,质数,筛法蓝桥杯国赛

[蓝桥杯 2025 国 B] 互质藏卡

题目描述

小蓝整理着阁楼上的旧物,偶然发现了一个落满灰尘的卡片箱。打开箱子,里面整齐地摆放着 17600 张卡片,每张卡片上都写有一个数字,恰好包含了从 1 到 17600 的所有正整数。

儿时的他热衷于收集各种卡牌,数量之多令人咋舌。如今,再次翻阅这些尘封的记忆,小蓝不禁感慨万千。他想起收藏家前辈的箴言:“收藏的魅力在于精粹,而非数量”。于是,他决定从这些卡牌中选取 20252025 张,组成一套“互质藏卡”。

“互质藏卡”的特点在于:任意两张卡片上的数字之间互质,即它们的最大公约数恒为 11。现在,请你帮小蓝计算,共有多少种不同的选取方案,使得选出的 20252025 张卡片满足“互质藏卡”的条件。由于答案可能很大,你只需给出其对 109+710^9 + 7 取余后的结果即可。

注意:两个选取方案被认为是不同的,当且仅当它们所包含的数字集合不完全相同。即,若存在至少一个数字出现在其中一个集合但不出现在另一个集合中,则这两个方案被视为不同。

输出格式

这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。