[BZOJ 4916]神犇和蒟蒻

Description

很久很久以前，有一只神犇叫yzy;

很久很久之后，有一只蒟蒻叫lty;

Input

请你读入一个整数N;1<=N<=1E9,A、B模1E9+7;

Output

请你输出一个整数 $A=\sum_{i=1}^N{\mu (i^2)}$ ;

请你输出一个整数 $B=\sum_{i=1}^N{\varphi (i^2)}$ ;

Sample Input

Sample Output

1
1

题解

首先注意到 $A$ 直接输出 $1$ 得满分。因为只有 $\mu(1^2)=1$ 。至于为什么，想想莫比乌斯函数是什么。

对于第二问容易发现 $\varphi(i^2)=i\cdot\varphi(i)$ 。至于为什么，想想你是怎么线性筛欧拉函数的。

对于函数 $f(i)=i\cdot\varphi(i)$ 容易发现，这也是个积性函数。我们可以将阈值内的线性筛筛出来。对于阈值外的，考虑杜教筛。

求 $S(n)=\sum\limits_{i=1}^nf(i)$

上述式子 $$g(1)S(n)=\sum_{i=1}^n(g*f)(i)-\sum_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$

考虑到 $\sum\limits_{d\mid n}\varphi(d)=n$ ，又由于 $(g*f)(n)=\sum\limits_{d\mid n}\varphi(d)d\cdot g\left(\frac{n}{d}\right)$ 。我们考虑让 $g(n)=id(n)$ ，那么 $(id*f)(n)=\sum\limits_{d\mid n}n\cdot\varphi(d)=n^2$ 。由于 $\sum\limits_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6}$ 。显然这个卷积的前缀为 $\sum\limits_{i=1}^n(g*f)(i)=\frac{n(n+1)(2n+1)}{6}$ 。

故对于 $f$ $$S(n)=\frac{n(n+1)(2n+1)}{6}-\sum_{i=2}^ni\cdot S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$

 //It is made by Awson on 2018.1.24

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Abs(a) ((a) < 0 ? (-(a)) : (a))

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

 #define writeln(x) (write(x), putchar('\n'))

 #define lowbit(x) ((x)&(-(x)))

 using namespace std;

 const int MOD = 1e9+;

 const int N = ;

 void read(int &x) {

     char ch; bool flag = ;

     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

     for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

     x *= -*flag;

 }

 void write(int x) {

     if (x > ) write(x/);

     putchar(x%+);

 }

 int n, inv2, inv6, f[N+];

 int prime[N+], isprime[N+], tot;

 map<int, int>mp;

 int quick_pow(int a, int b) {

     int ans = ;

     while (b) {

     if (b&) ans = 1ll*ans*a%MOD;

     a = 1ll*a*a%MOD, b >>= ;

     }

     return ans;

 }

 void get_f() {

     memset(isprime, , sizeof(isprime)); isprime[] = , f[] = ;

     for (int i = ; i <= N; i++) {

     if (isprime[i]) prime[++tot] = i, f[i] = 1ll*i*(i-)%MOD;

     for (int j = ; j <= tot && i*prime[j] <= N; j++) {

         isprime[i*prime[j]] = ;

         if (i%prime[j]) f[i*prime[j]] = 1ll*f[i]*(prime[j]-)%MOD*prime[j]%MOD;

         else {f[i*prime[j]] = 1ll*f[i]*prime[j]%MOD*prime[j]%MOD; break; }

     }

     (f[i] += f[i-]) %= MOD;

     }

 }

 int cal(int x) {

     if (x <= N) return f[x];

     if (mp.count(x)) return mp[x];

     int ans = 1ll*x*(x+)%MOD*(*x+)%MOD*inv6%MOD;

     for (int i = , last; i <= x; i = last+) {

     last = x/(x/i); (ans -= 1ll*(last+i)*(last-i+)%MOD*inv2%MOD*cal(x/i)%MOD) %= MOD;

     }

     return mp[x] = ans;

 }

 void work() {

     get_f(); inv2 = quick_pow(, MOD-), inv6 = quick_pow(, MOD-); read(n);

     writeln(); writeln((cal(n)+MOD)%MOD);

 }

 int main() {

     work();

     return ;

 }

巴特西