题解 P5218 【无聊的水题 II】
Aleph1022
·
·
题解
此文同步发表于我的博客：https://www.alpha1022.me/articles/lg-5218.htm
首先，容易证明裴蜀定理可以应用于 3 个及以上的整数间。
所以问题转化为有多少种选数的方案使得选出的数的 \gcd = 1。
设 f(x) 表示使得选出的数的 \gcd = x 的方案数，F(x) = \sum\limits_{x | d} f(d)。
由于 $\sum\limits_{i = 0}^n C_n^i = 2^n$，有 $F(x) = 2^{\lfloor \frac n x \rfloor} - 1$。
减一是为了剔除不选的情况。
于是有
$$\begin{aligned} & 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{aligned}$$
对于指数做数论分块，对于 $\mu$ 杜教筛就好了。
我的杜教筛比较偷懒直接上了 unordered_map（
代码：
```cpp
#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);
}
```