[BZOJ4916]神犇和蒟蒻 杜教筛/Min_25筛

题目大意：

给定(nle 10^9)，求：

1.(sum_{i=1}^nmu(i^2))

2.(sum_{i=1}^nvarphi(i^2))

解释

1.(sum_{i=1}^nmu(i^2))

直接输出1

因为对于(forall i>1)有(mu (i^2)=0)

2.(sum_{i=1}^nvarphi(i^2))

for 杜教筛：

构造函数(f(i)=varphi(i^2))，则有(f*mathrm{id}=id^2)，具体推导：

(sum_{d|n}varphi(d^2)frac n d=sum_{d|n}dvarphi(d)frac n d=nsum_{d|n}d=n^2)

杜教板子：（风格不太清真，好久以前写的）

#include <bits/stdc++.h>
#define maxn 3000010
#define p 1000000007
#define int long long
using namespace std;
 
map<int, long long> ans_phi;
bool vis[maxn];
int prime[maxn], tot;
long long phi[maxn];
long long inv2, inv6;
 
long long qpow(long long a, long long b)
{
    long long res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
 
void prework()
{
    inv2 = qpow(2, p - 2);
    inv6 = qpow(6, p - 2);
    phi[1] = 1;
    for (int i = 2; i <= 3000000; i++)
    {
        if (vis[i] == 0)
        { 
            prime[++tot] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= tot && prime[j] * i <= 3000000; j++)
        {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j] % p;
                break;
            }
            else
                phi[i * prime[j]] = phi[i] * (prime[j] - 1) % p;
        }
        phi[i] = i * phi[i] % p;
        (phi[i] += phi[i - 1]) %= p;
    }
}
 
long long S_phi(int n)
{
    if (n <= 3000000)
        return phi[n];
    if (ans_phi.count(n))
        return ans_phi[n];
    long long ans = 1LL * (2 * n + 1) * (n + 1) % p * n % p * inv6 % p;
    for (int l = 2, r; l <= n; l = r + 1)
    {
        r= n / (n / l);
        ans = ((ans - (r - l + 1) * (l + r) % p * S_phi(n / l) % p * inv2 % p) % p + p) % p;
    }
    return ans_phi[n] = ans;
}
 
void read(int &x)
{
    static char ch;
    x = 0;
    ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
}
 
signed main()
{
    prework();
//  int T;
//  read(T);
//  for (int n, i = 1; i <= T; i++)
//  {
        int n;
        read(n);
        printf("1
%lld
", S_phi(n));
//  }
    return 0;
}

for Min_25筛：

(f(p)=varphi(p^2)=pvarphi(p)=p^2-p)

对于质数我们需要筛一个g2，一个g1，方便判断质数最好再筛一个g0

快速计算(f(p^k))部分也可以参考Sum的Min_25筛写法

这题可以。。。写Min_25筛 后天再写