利用容斥原理求解 [a,b] 区间中与 n 互质的数字个数(HDU 4135 & ZOJ 3547)

先看这道丧心病狂的题目:HDU 4135 Co-prime。题目大意就是,有 T 组询问,每组询问给你三个数:a, b, c,问你闭区间 [a,b] 中有多少个数字与 n 互质。数据范围是:1 \leqslant A \leqslant B \leqslant 10^{15}1 \leqslant N \leqslant 10^5

乍一看毫无头绪,仿佛怎么做都会超时……其实用容斥的想法就很容易了~

斯特林数(Stirling Number)与放球问题,以及 HDU 4372 Count the Buildings 题解……

  • 你有 n 个不同的小球,现在你想用这些小球拼成 k 个环,一共有多少种拼法?
  • 你有 n 个不同的小球,现在你想将这些小球分成 k 个非空的集合,一共有多少种分法?

这两个问题就是最典型的斯特林数(Stirling Number)了。

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。