洛谷 5218 无聊的水题 II

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

设 f(x) 表示使得选出的数的 gcd=x 的方案数，F(x)=∑x|df(d)。
F(x) 其实就是选出的数都是 x 的倍数的方案数，显然 n 以内 x 的倍数有 ⌊nx⌋ 个。
由于 n∑i=0Cin=2n，有 F(x)=2⌊nx⌋−1。
减一是为了剔除不选的情况。

于是有 f(1)=n∑i=1μ(i)F(i)=n∑i=1μ(i)(2⌊ni⌋−1)

对于指数做数论分块，对于 μ 杜教筛就好了。
我的杜教筛比较偷懒直接上了 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);
}