GCD LCM 素数 快速幂

2018-07-23 05:31:05来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

1.**********  GCD(最大公约数)

 

代码实现(复杂度为O(logn))

 

int gcd ( int a, int b){

    return b ? gcd ( b , a % b ) : a ;

}

 

2.***********   LCM(最小公倍数) 

 

lcm(a,b) = a * b / gcd(a,b);

 

3.********   素数

 

代码实现(复杂度为O(logn))

 

函数isprime返回值中 值为1代表素数,值为0代表非素数

 

int isprime(int a){

    if(a==1) return 0;

    for(int i=2;i<=sqrt(a);i++){

        if(a%i==0) return 0;

    }

    return 1;

}

 

 

4.********素数打表

 

代码实现(复杂度为O(nloglogn))

 

数组nisprime中 值为0代表素数,值为1代表非素数

 

const int MAXN = (int)(打表范围);

int nisprime[MAXN];

void init() {

    nisprime[1] = 1;

    for(int i = 2; i < MAXN; i++) {

        if(!nisprime[i])

            for(long long j = i * i; j < MAXN; j += i) {

                nisprime[j] = 1;

            }

    }

}

 

//判断输入数值i是否为素数,只需判断nisprime[i]的值即可

 

5.********  快速幂

 

代码实现(复杂度为O(logn))

 

#define ll long long

ll poww(ll a,ll b,ll c){

    ll ant=1;

    while(b){

        if(b&1) ant = (ant * a ) % c;

        a=a*a%c;

        b>>=1;

    }

    return ant;

}

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:洛谷P4013 数字梯形问题(费用流)

下一篇:洛谷P2770 航空路线问题(费用流)