当前位置：首页 > article >正文

算法知识点————数论【最大公约数】【快速幂】【分解质因数】

article 2025/1/11 2:32:29

结论1：两个互质的整数mn不能凑出的最大整数是(n-1)(m-1) -1

结论2:一个数的因数可以拆成n个质因数的乘积。
在这里插入图片描述
黄金分割：0.61803399

在数论中，如果两个或两个以上的整数的最大公约数是 1 ，则称它们为互质。
最大公约数: 两数乘积=最大公约数*最小公倍数，如果是多个数的话就两个求完在和第三个求。

//辗转相除法
int gcd (int x,int y){
  int z = y;
  while(x%y != 0){
    z = x%y;
    x = y;
    y = z;
  }
  return z;
}

欧拉函数：小于等于n的正整数中与n互质的数的数目

在这里插入图片描述
快速幂算法logn
思想：每一步都把指数减半，而相应的底数做平方运算

typedef long long LL;

LL quick_qwp( LL a, LL b){
  LL res = 1;//任何数的0次幂都为1
  while(b > 0) {//逐位检查b的二进制位数
    if( b & 1){//检查b的最低位是否为1
     	 res = res*a;	 //如果b的最低位为1，则需要乘a
    }
    a = a*a;//底数a平方
    b>>1;//b右移一位
  }
  return res;
}

const int MOD=  998244353;
LL qpw(LL a,LL b){
    LL res =1;
    while( b > 0){
        if( b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b>>=1;
    }
    return res;
}

分解质因数

for(LL i =2 ;i*i <= n ;i++){
  if(n % i == 0){ // i 因数
    //cnt++；//（求质因数个数）
    while(n % i == 0) n/=i;
   // cout<<i<<" ";//输出质因数
  }
}
if( n > 1 ) cnt++;