2022.10.20

xingke233 / 2024-11-09 / 原文

练习情况

P3601 签到题

有意思的题目，先筛出 $10^6$ 的质数，每个质数对 $l$ ~ $r$ 的贡献。

每个质数在 $l$ ~ $r$ 下界是

$(\dfrac{(l-1)}{P}+1)P$

可以用分块思想理解

Code:

for(LL i=1;prime[i]*prime[i]<=r;i++){
        for(LL j=((l-1)/prime[i]+1)*prime[i];j<=r;j+=prime[i]){
            if(e[j-l]%prime[i]==0){
                phi[j-l]=(phi[j-l]/prime[i])*(prime[i]-1);
                while(e[j-l]%prime[i]==0) e[j-l]/=prime[i];
            }
        }
    }
    for(LL i=l;i<=r;i++){
        if(e[i-l]>1){phi[i-l]=(phi[i-l]/e[i-l])*(e[i-l]-1);}
        ans=(ans+i-phi[i-l])%mod;
     }

P1593 因子和

套用约数之和公式。

$\sum\limits_{d|n}^nd=\prod\limits_{i=1}^k \sum\limits_{j=1}^{a_i}p^j$

用等比数列求和公式求和。

$S_n=a_1\dfrac{1-p^n}{1-p}=\dfrac{p^n-1}{p-1}$。

因为要对 $9901$ 取模，所以用费马小定理求 $p-1$ 的逆元。

然后直接提交，喜提 $88$ 分。

回顾一下费马小定理需要的条件。

若 $p$ 为质数，$\gcd(a,p) = 1$，则 $a^{p-1} \equiv 1 \pmod{p}$。

当 $p-1$ 为 $9901$ 倍数的时候不存在逆元

所以此时要特判

ans=ans*(t+1)%mod;

Code:

P1593

P7868 [COCI2015-2016#2] VUDU

将 $a_i$ 减去 $p$，前缀和离散化丢树状数组里

Code:

P7868

P2303 [SDOI2012] Longge 的问题

欧拉反演

$n=\sum\limits_{d|n}\varphi(d)$

令 $n=\gcd(i,j)$

$\gcd(i,j)=\sum\limits_{d|gcd(i,j)}\varphi(d)$

$\gcd(i,j)=\sum\limits_{d|i}\sum\limits_{d|j}\varphi(d)$

由原问题可得

$\sum\limits_{i=1}^n\gcd(i,n)= \sum\limits_{i=1}^n\sum\limits_{d|i}\sum\limits_{d|n}\varphi(d)= \sum\limits_{d|n}\sum\limits_{i=1}^n\sum\limits_{d|i}\varphi(d)= \sum\limits_{d|n}\dfrac{n}{d}\varphi(d)$

如何理解

$\sum\limits_{i=1}^n\sum\limits_{d|i}\varphi(d)=\dfrac{n}{d}\varphi(d)$

考虑每个 $d$ 的贡献，$d|i$ 这样的 $i$ 在 $n$ 中有 $\left\lfloor\dfrac{n}{d}\right\rfloor$ 个。