练习情况

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\) 个。

Code:

P2303