洛谷 5218.无聊的水题 II

首先,容易证明裴蜀定理可以应用于 33 个及以上的整数间。
所以问题转化为有多少种选数的方案使得选出的数的 gcd=1\gcd = 1

f(x)f(x) 表示使得选出的数的 gcd=x\gcd = x 的方案数,F(x)=xdf(d)F(x) = \sum\limits_{x | d} f(d)
F(x)F(x) 其实就是选出的数都是 xx 的倍数的方案数,显然 nn 以内 xx 的倍数有 nx\lfloor \frac n x \rfloor 个。
由于 i=0nCni=2n\sum\limits_{i = 0}^n C_n^i = 2^n,有 F(x)=2nx1F(x) = 2^{\lfloor \frac n x \rfloor} - 1
减一是为了剔除不选的情况。

于是有

对于指数做数论分块,对于 μ\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
#include <cstdio>
#include <tr1/unordered_map>
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);
}