首先，容易证明裴蜀定理可以应用于 \(3\) 个及以上的整数间。
所以问题转化为有多少种选数的方案使得选出的数的 \(\gcd = 1\)。
设 \(f(x)\) 表示使得选出的数的 \(\gcd = x\) 的方案数，\(F(x) = \sum\limits_{x | d} f(d)\)。
\(F(x)\) 其实就是选出的数都是 \(x\) 的倍数的方案数，显然 \(n\) 以内 \(x\) 的倍数有 \(\lfloor \frac n x \rfloor\) 个。
由于 \(\sum\limits_{i = 0}^n C_n^i = 2^n\)，有 \(F(x) = 2^{\lfloor \frac n x \rfloor} - 1\)。
减一是为了剔除不选的情况。
于是有 \[\begin{align*} & f(1) \\ = & \sum\limits_{i = 1}^n \mu(i) F(i) \\ = & \sum\limits_{i = 1}^n \mu(i) (2^{\lfloor \frac n i \rfloor} - 1) \end{align*}\]
对于指数做数论分块，对于 \(\mu\) 杜教筛就好了。
我的杜教筛比较偷懒直接上了 unordered_map（
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
using namespace std;
using namespace tr1;
const long long N = 1e11;
const int CNT = 1e7;
const long long mod = 1e9 + 7;
long long n;
int vis[CNT + 5],prime[CNT + 5],cnt,mu[CNT + 5];
unordered_map<int,long long> w;
long long ans;
long long fpow(long long a,long long b)
{
a %= mod,b %= mod - 1;
long long ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = ret * a % mod),a = a * a % mod;
return ret;
}
long long calc(long long n)
{
if(n <= CNT)
return mu[n];
if(w.count(n))
return w[n];
long long ret = 1;
for(register long long l = 2,r;l <= n;l = r + 1)
{
r = n / (n / l);
ret = (ret - (r - l + 1) % mod * calc(n / l) % mod + mod) % mod;
}
return w[n] = ret;
}
int main()
{
mu[1] = 1;
for(register int i = 2;i <= CNT;++i)
{
if(!vis[i])
mu[prime[++cnt] = i] = -1;
for(register int j = 1;j <= cnt && i * prime[j] <= CNT;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
else
mu[i * prime[j]] = -mu[i];
}
}
for(register int i = 1;i <= CNT;++i)
mu[i] = (mu[i] + mu[i - 1] + mod) % mod;
scanf("%lld",&n);
for(register long long l = 1,r;l <= n;l = r + 1)
{
r = n / (n / l);
ans = (ans + (calc(r) - calc(l - 1) + mod) * (fpow(2,n / l) - 1) % mod) % mod;
}
printf("%lld\n",(ans + mod) % mod);
}