数论模板.docVIP

数论： 最大公倍数与最小公倍数： int gcd(int x,int y){??? int z;??? while(x%y){??????? z=y;??????? y=x%y;??????? x=z;??? }??? return y;}int lcm(int x,int y){??? return x/gcd(x,y)*y;} //简单素数判定 bool Isprime(int n){??? int i;??? for(i=2;iint(sqrt(n))+1;++i)??????? if(n%i==0)return false;??? return true;} 乘方运算： unsigned Power(unsigned n, unsigned p) { // 计算n的p次方??? unsigned odd = 1; //oddk用来计算“剩下的”乘积??? while (p 1){ // 一直计算到指数小于或等于1?????? if (( p 1 )!=0){ // 判断p是否奇数，偶数的最低位必为0???????????? odd *= n; // 若odd为奇数，则把“剩下的”乘起来???? ?? }????? n *= n; // 主体乘方????? p /= 2; // 指数除以2???? }??? return n * odd; // 最后把主体和“剩下的”乘起来作为结果}unsigned Montgomery(unsigned n,unsigned p,unsigned m){ //快速计算(n^e)%m的值????? unsignedk=1;????? n%=m;??? while(p!=1){??????? if(0!=(p1))k=(k*n)%m;??????? n=(n*n)%m;??????? p=1;??? }??? return(n*k)%m;}#include stdio.h #include stdlib.h //求a^b除以n的约数 //采用二进制提高效率类似于求a的b次方，减少循环次数 int modExp(int a, int b, int n) { int iresult = 1; int itemp = a % n; while (b 0) { if (b % 2 == 1) { iresult = (iresult * itemp) % n; } itemp = (itemp * itemp) % n; b /= 2; } return iresult; } int passMillerRabinTest(int n) { int l, m, b, i, k; //令大奇数n = (2^l) * m + 1, m是正奇数， m = n - 1; l = 0; while (m % 2 == 0){ l += 1; m /= 2; } b = rand() + 1; //随机生成b if (modExp(b, m, n) == 1) { return 1; } k = m; for (i = 0; i = l - 1; i++) { if (modExp(b, k, n) == n - 1) { return 1; } k *= 2; } return 0; } int main() { int x; while(scanf(%d, x)) { if (passMillerRabinTest(x)) { printf(素数\n); } else { pri