背诵内容

wukaichen888 · 2024-02-20 23:03:05 · 个人记录

我没有数论基础我没有数论基础我没有数论基础

今天 sbh 教我学数论，这是写给自己看的

剩下忘了，写到就补

\varphi(x)=\Pi_{i=1}^k(p_i-1)p_i^{c_i-1}
\mu(x)=\Pi_{i=1}^k[c_i=1](-1)^{c_i}

都是积性函数

[x=1]=\sum_{d|x}\mu(d)
g(n)=\sum_{d|n}f(d)$，则 $f(n)=\sum_{d|n}\mu(\frac{n}{d})g(d)
\lfloor \frac{n}{i}\rfloor=\lfloor \frac{n}{j}\rfloor$，$j_{max}=\lfloor\frac{n}{\frac{n}{i}}\rfloor

int p[R],cnt;
int phi[R],mu[R];
ll s[R],res;
bool b[R];
void get_p(){
    for(int i=1;i<R;i++) b[i]=1;
    b[1]=0;
    phi[1]=mu[1]=1;
    for(int i=2;i<R;i++){
        if(b[i]){
            p[++cnt]=i;
            phi[i]=i-1;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*p[j]<R;j++){
            b[i*p[j]]=0;
            if(!(i%p[j])){
                phi[i*p[j]]=phi[i]*p[j];
                mu[i*p[j]]=0;
                break;
            }
            phi[i*p[j]]=phi[i]*(p[j]-1);
            mu[i*p[j]]=-mu[i];
        }
    }
}

https://www.luogu.com.cn/blog/An-Amazing-Blog/mu-bi-wu-si-fan-yan-ji-ge-ji-miao-di-dong-xi

https://zhuanlan.zhihu.com/p/138897504

\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)

\sum_{d}^{\min(n,m)}\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{d}\times[\gcd(i,j)=d]

\sum_{d}^{\min(n,m)}d(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\times[\gcd(i,j)=1])

\sum_{d}^{\min(n,m)}d(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\sum_{e|i,e|j}\mu(e))

\sum_{d}^{\min(n,m)}d(\sum_e^{\lfloor\frac{min(n,m)}{d}\rfloor}\mu(e)(\sum_{e|i}^{\lfloor\frac{n}{d}\rfloor}\sum_{e|j}^{\lfloor\frac{m}{d}\rfloor}ij))

\sum_{d}^{\min(n,m)}d(\sum_e^{\lfloor\frac{min(n,m)}{d}\rfloor}\mu(e)e^2\frac{\lfloor\frac{n}{ed}\rfloor( \lfloor\frac{n}{ed}\rfloor+1)\lfloor\frac{m}{ed}\rfloor( \lfloor\frac{m}{ed}\rfloor+1)}{4}

令 T=ed

\sum_{T}^{\min(n,m)}\frac{\lfloor\frac{n}{T}\rfloor( \lfloor\frac{n}{T}\rfloor+1)\lfloor\frac{m}{T}\rfloor( \lfloor\frac{m}{T}\rfloor+1)T}{4}\sum_{e|T}(\mu(e)\times e)

令 g(x)=\sum_{d|x}(\mu(d)\times d)