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

结论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次幂都为1while(b > 0) {//逐位检查b的二进制位数if( b & 1){//检查b的最低位是否为1res = 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++;