笔记数论1

· · 个人记录

a/b\%p=a*inv(b)=a*b^{p-2}\%p (a*b)\%p=(a\%p)*(b\%p)\%p φ(n)=n*((p_1-1)/p_1)*……*((p_m-1)/p_m) φ(abc)=φ(a)*φ(b)*φ(c) (isprime(a,b,c) φ(n*m)=φ(n)*φ(m) i\%p==0,φ(i*p)=p*φ(i) x,p$互质，则有 $x^{φ(p)}\equiv1(modp)

欧拉老贼非人哉

若p为质数，且a,p互质则 a^{(p-1)}\equiv1(mod p)

显然1^p\equiv1(modp)成立，假定a^{(p-1)}\equiv 1(modp)成立

那么只要推出(a+1)^{p-1}\equiv1(modp)

a^p\equiv a(mod p) (a+1)^p=C_p^0a^0+C_p^1a^1+C_p^2a^2+...+C_p^{p-1}a^{p-1}+C_p^pa^p (a+1)^p\equiv(1+a^p)(modp) (a+1)^p\equiv (1+a)(modp)

使用线性筛扇欧拉老贼

筛素数，φ(n)，因子乘积

bool st[N];int prime[N],phi[N],cnt;
void sss(int n) {
    memset(st, 1, sizeof(st));
    st[1] = 0;
    for(int i = 2; i <= n; i++) {
        if(st[i])prime[++cnt] = i,phi[i]=i-1;
        for(int j = 1; j <= cnt && i*prime[j] <= n; j++) {
            st[i*prime[j]] = 0;
            if(i % prime[j] == 0){
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

我也不知道他是来干司马德

const int N = 1001;
bool st[N];
int prime[N],a[N],d[N],cnt;
void sss(int n){
    d[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i])prime[++cnt]=i,a[i]=1,d[i]=2;
        for(int j=1;prime[j]<=n/i;j++){
            int m=i*prime[j];st[m]=1;
            if(i%prime[j]==0){
                a[m]=a[i]+1,d[m]=d[i]/a[m]*(a[m]+1);
                break;
            }else a[m]=1,d[m]=(a[m]+1)*d[i];
        }
    }
}

莫比乌斯函数

定义 \mu(n)

性质\mu(ab)=\mu(a)\mu(b)\

\begin{aligned} &1 & &n=1 \cr &0 & &n\neq1 \cr \end{aligned} \right.

对于任意正整数n有:

\sum_{d|n}\frac{\mu(d)}{d}=\frac{φ(n)}{n}

求法

i$是质数 $\mu(i)=(-1)^1=-1 令m=i*prime_j

1.若i\%prime_j == 0m中至少包含一个prime_j所以\mu(m)=0

2.写不下去了好心人帮个忙qwq

--用c++囸莫比乌斯-- 
int n,p[N],vis[N],cnt;
int mu[N];
void getmu(int n){
    mu[i]=1;
    for(int i=2;i<=n;i++){
        if(vis[i])p[++cnt]=i,mu[i]=-1;
        for(int j=1;i*p[j]<=n;j++){
            int m=i*p[j];
            vis[m]=1;
            if(i%p[j]==0){
                mu[m]=0;
                break;
            }else mu[m]=-mu[i];
        }
    }
}

整除分块复杂度 O(n)

f(i)指对i去重后的项目数 - 当 $i\leq \sqrt{n}$ 有$\sqrt{n}($即$i=1-\sqrt{n})$种情况 - 当 $i> \sqrt{n}$ $\lfloor \frac{n}{i} \rfloor < \sqrt n$最多有$\sqrt n$种情况 - 情况1+情况2$\leq 2 \sqrt{n} $R_n=\lfloor \frac{n}{k}\rfloor L_n=L_{n-1}+1