SPOJ INTSUB - Interesting Subset（数学）

http://www.spoj.com/problems/INTSUB/en/

题意：给定一个集合，该集合由1,2,3....2n组成，n是一个整数。问该集合中有趣子集的数目，答案mod1e9+7。

x的子集合有趣定义为，该子集中至少有两个数，a和b，b是a的倍数且a是集合中最小的元素。

思路：考虑集合中最小的元素a，对于每个a，使得可以构成子集的元素（即b）有beishu = 2 * n / a - 1个，那么这里只考虑这些有2^beishu - 1个。那么还剩下other = 2 * n - beishu - a个比a大的且不是a的倍数的元素，这些元素可以取或者不取，因此有2^other种。两个相乘即可以得到最小元素为a时候的子集数。

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int MOD = ;

 LL biao[];

 int main() {

     int t;

     scanf("%d", &t);

     biao[] = ;

     for(int i = ; i <= ; i++) {

         biao[i] = biao[i-] << ;

         biao[i] %= MOD;

     }

     for(int cas = ; cas <= t; cas++) {

         int n;

         scanf("%d", &n);

         LL ans = ;

         for(int i = ; i <= n; i++) {

             int beishu =  * n / i - ; // 是i的倍数的个数

             int other =  * n - beishu - i; // 不是i的倍数并且大于i的个数

             ans = biao[other] * (biao[beishu] - ) % MOD + ans; // beishu有选和不选两种,因此是2^beishu种,因为不能全部不选,所以-1,其他的有选不选两种,是2^other

             ans %= MOD;

         }

         printf("Case %d: %lld\n", cas, ans);

     }

     return ;

 }