09 绝对序号
127是个很有意思的数。首先，它是一个质数。在质数集合中，127是第31个质数，31又是第11个质数，11是第5个，5是第3个，3是第2个，2是第1个，1不是质数。
如上所示，序号的定义是集合中不大于该数的元素个数。如果某数在集合中的序号仍然在这个集合中，序号的序号也在这个集合中，序号的序号的序号……全都在这个集合中，最终通过有限次求序号操作后得到1，而1不在这个集合中。那么，就称该数在此集合中拥有绝对序号。
已知 n ，求 n 在集合 {2, 3, 4, ..., n} 的多少个子集中拥有绝对序号。由于计算结果很大，只需要回答子集个数除以 100003 的余数。
输入格式：
第一行为测试样本数量 T ，以下 T 行每行包含一个整数 n 。
输出格式：
每一行为 Case #x: y 的格式，其中 x 为1开始的测试样本序号，y 如上所述。
限制条件：
1 ≤ T ≤ 100
2 ≤ n ≤ 500
示例输入：
2
5
6
示例输出：
Case #1: 5
Case #2: 8
示例解释：
第一个例子中，5在{2, 3, 4, 5}{2, 3, 5}{3, 4, 5}{2, 5}{5} 这5个集合中拥有绝对序号。
第二个例子中，6在{2, 3, 4, 5, 6}{2, 3, 4, 6}{2, 4, 5, 6}{2, 3, 6}{3, 4, 6}{3, 5, 6}{2, 6}{6} 这8个集合中拥有绝对序号。
[ 本帖最后由 周瑜 于 2010-6-7 10:37 编辑 ]
 附件:
09 绝对序号.rar (2010-6-7 22:37, 797 bytes)
该附件被下载次数 108
|
