[BZOJ 3944]Sum-白红宇

[BZOJ 3944]Sum

阅读量：5066 次

发布时间：2019-06-12

本文共 2925 字，大约阅读时间需要 9 分钟。

Description

求 $ans1=\sum\limits_{i=1}^n \varphi(i)$ 和 $ans2=\sum\limits_{i=1}^n \mu(i)$ 。 $n<2^{31}$ ，多组询问。

Input

一共T+1行

第1行为数据组数T(T<=10)

第2~T+1行每行一个非负整数N，代表一组询问

Output

一共T行，每行两个用空格分隔的数ans1,ans2

Sample Input

2333

Sample Output

1 1

2 0

22 -2

58 -3

278 -3

1655470 2

题解

杜教筛的板子。已经有许多博客有讲，我也不凑这个热闹了。

记 $S_n$ 为积性函数的前缀。

对于 $\mu$ ： $$S(n)=1-\sum_{i=2}^nS\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$

对于 $\varphi$ ： $$S(n)=\frac{n(n+1)}{2}-\sum_{i=2}^nS\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$

取 $2333333$ 作为阈值，线性筛出之前的，然后记忆化之后的。

1 //It is made by Awson on 2018.1.24 2 #include 
     
       3 #include 
       4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               
                13 #include 
                
                 14 #include 
                 
                  15 #define LL long long16 #define Abs(a) ((a) < 0 ? (-(a)) : (a))17 #define Max(a, b) ((a) > (b) ? (a) : (b))18 #define Min(a, b) ((a) < (b) ? (a) : (b))19 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))20 #define writeln(x) (write(x), putchar('\n'))21 #define lowbit(x) ((x)&(-(x)))22 using namespace std;23 const int N = 2333333;24 void read(LL &x) {25 char ch; bool flag = 0;26 for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());27 for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());28 x *= 1-2*flag;29 }30 void write(LL x) {31 if (x > 9) write(x/10);32 putchar(x%10+48);33 }34 35 LL mu[N+5], phi[N+5], n;36 struct num {37 LL ans1, ans2;38 num() {}39 num(LL _ans1, LL _ans2) {ans1 = _ans1, ans2 = _ans2; }40 }ans;41 map
                  
                   mp;42 43 int prime[N+5], isprime[N+5], tot;44 void get_pre() {45 memset(isprime, 1, sizeof(isprime)); isprime[1] = 0, mu[1] = phi[1] = 1;46 for (int i = 2; i <= N; i++) {47 if (isprime[i]) prime[++tot] = i, mu[i] = -1, phi[i] = i-1;48 for (int j = 1; j <= tot && i*prime[j] <= N; j++) {49 isprime[i*prime[j]] = 0;50 if (i%prime[j]) mu[i*prime[j]] = -mu[i], phi[i*prime[j]] = phi[i]*(prime[j]-1);51 else {mu[i*prime[j]] = 0, phi[i*prime[j]] = phi[i]*prime[j]; break; }52 }53 mu[i] += mu[i-1], phi[i] += phi[i-1];54 }55 }56 num Less (const num &a, const num &b) {num ans; ans.ans1 = a.ans1 - b.ans1, ans.ans2 = a.ans2-b.ans2; return ans; }57 num Times (const num &a, const LL &x) {num ans; ans.ans1 = a.ans1*x , ans.ans2 = a.ans2*x; return ans; }58 num cal(LL x) {59 if (x <= N) return num(phi[x], mu[x]);60 if (mp.count(x)) return mp[x];61 num ans = num(x*(x+1)/2, 1);62 for (LL i = 2, last; i <= x; i = last+1) {63 last = x/(x/i); ans = Less(ans, Times(cal(x/i), (last-i+1)));64 }65 return mp[x] = ans;66 }67 void work() {68 read(n); ans = cal(n);69 write(ans.ans1), putchar(' ');70 if (ans.ans2 < 0) putchar('-'), writeln(-ans.ans2);71 else writeln(ans.ans2);72 }73 int main() {74 get_pre(); LL t; read(t);75 while (t--) work();76 return 0;77 }