简单数学函数

wangbinfeng · 2023-07-30 10:44:19 · 算法·理论

1. 最大公约数（gcd）：

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

2. 最小公倍数（lcm）：

int lcm(int a,int b) {
    return a/gcd(a,b)*b;           //注意：除数为gcd(a,b)
}

3. 快速幂：

   template<typename A,typename B,typename C>
   C pow(A x,B y,C p){
   if(x==0)return 0;
   if(y==0)return 1;
   C ret=pow(x,y/2,p);
   return ret*ret%p*(y%2?x:1)%p;
   }

   PS. 例题： P1226 【模板】快速幂 | 取余运算

4. log_2

   for (int i = 1; i <= n; i++)
       lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);