算法常用模板

冷不防 2023-10-04 08:55 50阅读 0赞

### 第四部分：数学知识 ###

**一.质数问题**  
（1）试除法判定质数

int is_prime(int n)
    {
        
         if(n<2) return false;
         for(int i=2;i<=n/i;i++)
              if(n%i==0) return false;
         return true;
    }

（2）试除法分解质因数

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

**二.素数问题**  
（1）朴素筛法求素数

int primes[N],cnt;
    bool st[N];
    
    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;
         }
    }

（2）线性筛法求素数

int primes[N],cnt;
    bool st[N];
    
    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;
              }
         }
    }

**三.约数问题**  
（1）试除法求所有约数

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

（2）约数个数和约数之和

如果 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)

**四.欧几里得算法**  
（1）欧几里得算法

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

（2）扩展欧几里得算法

在这里插入代码片

**五.快速幂**

求 m^k mod p，时间复杂度 O(logk)。
    int qmi(int a,int b,int q);
    {
        
         int res=1%q;
         while(b)
         {
        
              if(b&1) res=(LL)res*a%q;
              a=(LL)a*a%q;
              b>>=1;
         }
         return res;
    }

**六.组合数问题**  
（1）递归法求组合数

for(int i=0;i<N;i++)
         for(int j=0;j<N;j++)
         if(!j) C[i][j]=0;
         else C[i][j]==(C[i-1][j]+C[i-1][j-1])%mod;

（2）通过预处理逆元的方式求组合数  
（3）Lucas定理  
（4)分解质因数法求组合数

转载自：[AcWing][]

[AcWing]: https://www.acwing.com/blog/content/406/