自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 22:08:22，当前版本为作者最后更新于2019-05-10 22:15:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

此文同步发表于我的博客：https://www.alpha1022.me/articles/lg-5218.htm

首先，容易证明裴蜀定理可以应用于 $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{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（

代码：

#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);
}