【题解】51Nod 1594 莫比乌斯反演

逃离我推掉我的手 2023-08-17 16:49 129阅读 0赞

## Updated：这只鸽子学会了LaTeX ##

题意

求

$$\\sum\_\{i=1\}^\{n\} \\sum\_\{j=1\}^\{n\} \\phi(gcd(\\phi(i),\\phi(j)))$$

在草稿纸上一番乱划推导之后

$$\\sum\_\{i=1\}^\{n\} \\sum\_\{j=1\}^\{n\} \\phi(gcd(\\phi(i),\\phi(j)))$$

$$=\\sum\_\{d=1\}^\{n\} \\phi(d)\{\\times\}f(d)$$

这里f(d)表示有多少对i，j满足他们的$\\phi$值的gcd为d

$$f(d)=\\sum\_\{i,j\} \{\\lbrack\} \{gcd(\\phi(i),\\phi(j))=d\} \{\\rbrack\}$$

我们令

$$F(d)=\\sum\_\{i,j\}\{\\lbrack\}\{d\{\\vert\}gcd(\\phi(i),\\phi(j))\}\{\\rbrack\}$$

就有

$$F(n)=\\sum\_\{n\{\\vert\}d\} f(d)$$

反演得到

$$f(n)=\\sum\_\{d\} F(n\{\\times\}d)\{\\times\}\\mu(d)$$

所以原式就等于

$$\\sum\_\{i\{\\times\}j<=n\} \\phi(i)\{\\times\}F(i\{\\times\}j)\{\\times\}\\mu(j)$$

只需要预处理出$\\mu , \\phi $ 和F即可

code

1 //
     2 //  main.cpp
     3 //  51nod
     4 //
     5 //  Created by gengyf on 2019/8/8.
     6 //  Copyright © 2019 yifan Geng. All rights reserved.
     7 //
     8 
     9 #include <iostream>
    10 using namespace std;
    11 namespace gengyf{
    12 #define maxn 2000010
    13 #define ll long long
    14     inline int read(){
    15         int f=1,x=0;char s=getchar();
    16         while(s<'0'||s>'9'){
        if(s=='-')f=-1;s=getchar();}
    17         while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    18         return f*x;
    19     }
    20     ll w[maxn>>2],miu[maxn],phi[maxn],c[maxn],vis[maxn];
    21     int n,T,t;ll ans;
    22     void init(){
    23         phi[1]=miu[1]=1;
    24         for(int i=2;i<=maxn;i++){
    25             if(!vis[i]){
        //如果是质数
    26                 miu[++w[++t]=i]=-1;
    27                 phi[i]=i-1;
    28             }
    29             for(int j=1,k;(k=i*w[j])<=maxn;j++){
    30                 vis[k]=1;
    31                 if(i%w[j]==0){
    32                     phi[k]=phi[i]*w[j];
    33                     miu[k]=0;break;
    34                 }
    35                 phi[k]=phi[i]*(w[j]-1);miu[k]=-miu[i];
    36             }
    37         }
    38     }
    39     ll F(int x){
        return c[x]*c[x];}
    40     ll calc(int n){
    41         memset(c,0,sizeof(c));
    42         ans=0;
    43         for(int i=1;i<=n;i++){
    44             ++c[phi[i]];
    45         }
    46         for(int i=1;i<=n;i++)
    47             for(int j=i+i;j<=n;j+=i){
    48                 c[i]+=c[j];
    49             }
    50         for(int i=1;i<=n;i++){
    51             if(miu[i])
    52                 for(int j=1;i*j<=n;j++){
    53                     ans+=F(i*j)*miu[i]*phi[j];
    54                 }
    55         }
    56         return ans;
    57     }
    58     int main(){
    59         init();
    60         T=read();
    61         while(T--){
    62             n=read();
    63             printf("%lld\n",calc(n));
    64         }
    65         return 0;
    66     }
    67 }
    68 int main(){
    69     gengyf::main();
    70     return 0;
    71 }

推式子很有趣的，大家一起来推式子啊

手动滑稽.jpg

转载于:https://www.cnblogs.com/gengyf/p/11329759.html