发布时间：2023-11-09

质数

试除法判断质数 $O(\sqrt{N})$

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )//写i*i<=x容易爆int,写i<=sqrt(x)太慢
        if (x % i == 0)
            return false;
    return true;
}

试除法分解质因数 $O(logN) -O(\sqrt{N})$

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

埃氏筛筛质数 $O (N\sqrt{N})$

原理：每次将i的倍数筛去

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

质数筛 $O(N)$

原理：保证每个数都是被其最小的质因数筛去
证明：
当 i%prime[j]==0时,由于质数从小到大枚举，因此prime[j]必定是i的最小质因数,也必定是i*prime[j]最小质因数 当i%prime[j]!=0时,也可以发现仍然为最小质因数

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

试除法求所有约数 $O(\sqrt{N})$

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

约数个数和约数之和

如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

求约数之和

等比数列求和

复杂度：$O(KlogN)$

分治做法

。。。。。。。。

欧几里得求GCD $O(logN)$

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

求欧拉函数 $O(\sqrt{N})$

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

筛法求欧拉函数

int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            /*
            prime[j]为i的质因子，
            根据公式phi(N)=N*(1-1/p)*...,
            只需改变N即N1=N*prime[j],
            phi(N1)=phi(N)*prime[j]
            */
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            /*
            否则，N需要乘上prime[j]的同时，
            还需乘上多一个质因子的贡献(1-1/prime[j])
            即乘上prime[j]-1
            */
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

欧拉定理

$若a与n互质，则有a^{\phi(n)} \equiv 1 (mod n)$

P3601 签到题

题意：
$f(x)表示小于等于x且与x不互质的数，即x- \phi (x)$
$1 \leq l \leq r \leq 10^12 ,r-l \leq 10^6$
思路：

• 大于 $\sqrt r$ 的质因数只有一个，因此先把小于等于的质因数筛出来，算贡献
• 大于的特判即可
• $O(1e6+(1e6)log(1e6))$

vector<int> prime;
bool vis[N];
void sieve(){
    for(int i=2;i<N;i++){
        if(!vis[i]){
            vis[i]=1;
            prime.push_back(i);
        }
        for(int j=0;j<prime.size()&&prime[j]*i<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int phi[N],val[N],l,r;
void work(){
    for(auto &p:prime){
        for(int i=(l+p-1)/p*p;i<=r;i+=p){
            phi[i-l]/=p;
            phi[i-l]*=p-1;
            while(val[i-l]%p==0)val[i-l]/=p;
        }
    }
}
void solve(){
    cin>>l>>r;
    sieve();
    for(int i=l;i<=r;i++)val[i-l]=phi[i-l]=i;
    work();
    int ans=0;
    for(int i=l;i<=r;i++){
        if(val[i-l]>1)phi[i-l]/=val[i-l],phi[i-l]*=val[i-l]-1;// 特判大质因子
        (ans+=i-phi[i-l])%=mod;
    }
    cout<<ans<<"\n";
}

P3653 小清新数学题

题意：
求l到r的莫比乌斯函数和，但是l，r范围1e18
思路：

• 筛出1e6的质数
• 剩下的大数有四种可能：
  • 1：1
  • 平方数：0
  • 质数：-1，使用miller-rabin检验
  • 两个质数：0

vector<int> prime;
bool vis[N];
void sieve(){
    for(int i=2;i<N;i++){
        if(!vis[i]){
            vis[i]=1;
            prime.push_back(i);
        }
        for(int j=0;j<prime.size()&&prime[j]*i<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int mu[N],val[N],l,r;
void work(){
    for(auto &p:prime){
        for(int i=(l+p-1)/p*p;i<=r;i+=p){
            int cnt=0;
            while(val[i-l]%p==0)val[i-l]/=p,cnt++;
            if(cnt==1)mu[i-l]=-mu[i-l];
            else mu[i-l]=0;
        }
    }
}
__int128 qpow(__int128 a,int b,int mod){
    if(mod==1)return 0;
    __int128 ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}
bool MillerRabin(int n){
    if(n<=1)return false;
    if(n%2==0&&n!=2)return false;
    static constexpr int base[9]={2,3,5,7,11,13,17,37,61};
    for(auto &a:base){
        if(n==a)return true;
    }
    int d=n-1;
    while(d%2==0)d/=2;
    for(auto &a:base){
        int t=d;
        __int128 y=qpow(a,t,n);
        while(t!=n-1&&y!=1&&y!=n-1){
            y=y*y%n;
            t<<=1;
        }
        if(y!=n-1&&t%2==0)return false;
    }
    return true;
} 
int Mobius(int x){
    if(x==1)return 1;
    int sq=sqrt(x);
    if(sq*sq==x)return 0;
    if(MillerRabin(x))return -1;
    return 1;
}
void solve(){
    cin>>l>>r;
    sieve();
    for(int i=l;i<=r;i++)mu[i-l]=1,val[i-l]=i;
    work();
    int ans=0;
    for(int i=l;i<=r;i++){
        ans+=Mobius(val[i-l])*mu[i-l];
    }
    cout<<ans<<"\n";
}