http://www.spoj.com/problems/TFSETS/ Brief description: 求有多少 {1..n} 的子集，满足若 x 在该子集中，则 2x 和 3x 不在该子集中。（n ≤ 100000） Analysis: 同 HNOI 2012. 集合选数 需要预处理 + 二分查找。。。。。 首先考察所有。。。 2^a 3^b 1 2 3 4 6 9 8 … 那么 f(x) 的结果三角形填数。。要求相邻格子不能同时为 1.。的方案数。。。。 对于所有非 2^a 3^b 的数 p。。。它和所有的。。p 2^a 3^b 又可以形成一组三角形。。彼此独立。。乘法原理。。 且……