无聊的水题。
根据裴蜀定理，显然能组合出任意值的充要条件是，选出的数的 \(\gcd = 1\)。
设 \(g(i)\) 为在 \(1 \sim n\) 中选出若干个数使得它们 \(\gcd = i\) 的方案数，\(f(i)\) 为在 \(1 \sim n\) 中选出若干个数使得它们 \(\gcd\) 是 \(i\) 的倍数的方案数。我们有：
\[f(i) = \sum\limits_{i \mid j} g(j) = 2^{\left\lfloor\frac{n}{i}\right\rfloor} - 1 \]\[g(i) = \sum\limits_{i \mid j} \mu(\frac{j}{i}) f(j) \]因此：
\[g(1) = \sum\limits_{i = 1}^n \mu(i) (2^{\left\lfloor\frac{n}{i}\right\rfloor} - 1) \]整除分块后使用杜教筛计算 \(\mu(i)\) 前缀和，复杂度 \(O(\sqrt{n} \log n + n^{\frac{2}{3}})\)。
code
// Problem: P5218 无聊的水题 II
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5218
// Memory Limit: 500 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 30000100;
const int N = 30000000;
const ll mod = 1000000007;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll pr[maxn / 10], tot, mu[maxn], n;
bool vis[maxn];
unordered_map<ll, ll> mp;
ll dfs(ll n) {
if (n <= N) {
return mu[n];
}
if (mp.find(n) != mp.end()) {
return mp[n];
}
ll res = 1;
for (ll i = 2, j; i <= n; i = j + 1) {
j = n / (n / i);
res = (res - (j - i + 1) % mod * dfs(n / i) % mod + mod) % mod;
}
return mp[n] = res;
}
void solve() {
mu[1] = 1;
for (int i = 2; i <= N; ++i) {
if (!vis[i]) {
pr[++tot] = i;
mu[i] = mod - 1;
}
for (int j = 1; j <= tot && i * pr[j] <= N; ++j) {
vis[i * pr[j]] = 1;
if (i % pr[j] == 0) {
mu[i * pr[j]] = 0;
break;
}
mu[i * pr[j]] = mod - mu[i];
}
}
for (int i = 1; i <= N; ++i) {
mu[i] = (mu[i] + mu[i - 1]) % mod;
}
scanf("%lld", &n);
ll ans = 0;
for (ll i = 1, j; i <= n; i = j + 1) {
j = n / (n / i);
ans = (ans + ((dfs(j) - dfs(i - 1)) % mod + mod) % mod * (qpow(2, n / i) + mod - 1) % mod) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}