【题目链接】 点击打开链接

【题意】给定一个集合，该集合由1,2,3....2n组成，n是一个整数。问该集合中有趣子集的数目，答案mod1e9+7。x的子集合有趣定义为，该子集中至少有两个数，a和b，b是a的倍数且a是集合中最小的元素。

【解题方法】考虑一下枚举一个最小元素，那么比它大的元素的个数显然为（2*n / a-1）。这其中的元素有选和不选两种，但是不能全部不选。接下来是所有大于最小元素的元素并且不是最小元素倍数的数，可以随便侠，于是公式就呼之欲出了。


//
//Created by just_sort 2016/1/2
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
const int maxn = 100010;
const int maxm = 2e5;
const int maxs = 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9+7;
int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);}
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
int f[2001];
int main()
{
    f[0] = 1;
    REP2(i, 1, 2000) f[i] = (f[i - 1] << 1) % mod;
    int n, tt, ks = 0;
    scanf("%d", &tt);
    while(tt--){
        scanf("%d", &n);
        int ans = 0;
        REP2(i, 1, n){
            ans += (1LL * ((f[2 * n / i - 1] - 1) % mod) * 1LL * (f[2 * n - i - 2 * n / i + 1] % mod)) % mod;
            ans %= mod;
        }
        if(ans < 0) ans += mod;
        printf("Case %d: %d\n", ++ks, ans);
    }
    return 0;
}