先看这道丧心病狂的题目：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$。
乍一看毫无头绪，仿佛怎么做都会超时……其实用容斥的想法就很容易了～
先看这道丧心病狂的题目：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$。
乍一看毫无头绪，仿佛怎么做都会超时……其实用容斥的想法就很容易了～