大数的幂取模

Posted on   |   In   |  

数的幂取模和素数的相关内容
算法中相应的数学方法

大数的幂取模和素数的相关内容

基本的模运算

将a和b除以m后所得的余数相等记作$a\equiv b(mod\ m)$, 将a除以m所得的余数记作$a\ mod\ m$,并规定$0 \leq a\ mod\ m\leq m-1$。假设$a\equiv c(mod\ m)$且$b\equiv d(mod\ m)$,那么有下面的等式成立：
$$a+b \equiv c+d (mod\ m)$$
$$a-b \equiv c-d (mod\ m)$$
$$a*b \equiv c*d (mod\ m)$$

快速幂运算

反复平方法

我们把对任意的1 < x < n都有$ x^n\equiv x(mod\ n) $成立的合数n称为Carmicheal Number。对于给定的整数n，请判断它是不是Carmichael Number.

此题中，最为关键的就是如何求出$x^n\ mod\ n$的问题，因为很有可能这个幂会溢出
考虑加速幂运算的方法，同时保证不溢出。在$ n = 2^k$的条件下，有
$$ x^n = ((x^2)^2)…$$
由此，我们可以将n表示为
$$ n = 2^{k_1}+2^{k_2}+2^{k_3}….$$
利用
$x*y\ mod\ m = (x\ mod\ m) * (y\ mod\ m)\ mod\ m$
的原理
利用公式$a*b\%c=((a\%c)*b)\%c$,这样每一步都进行这种处理，这就解决了a^b可能太大存不下的问题
例如$x^{22}= x^{16} * x^4 * x^2$（22转换为2进制为10110）,从而转换为
{$x^{22} \% m = (x^2 \%m) * ({x^4 \% m}) * (x^{16} \% m)\ \% m$,从而进行迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
//时间复杂度O(logn)

typedef long long ll;

ll mod_pow(ll x, ll n, ll mod){
    ll res = 1;
    while(n > 0){
        if (n & 1) res = res * x % mod;  //标记为1，则计算此位上的余数，并与之前的余数迭代
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

第二种方法利用了二分的思想，可以达到O(logn)

1
2
3
4
5
6
7
8
typedef long long ll;

ll mod_pow(ll x. ll n, ll mod){
    if(n == 0) return 1;
    ll res = mod_pow(x * x % mod, n/2, mod);   //防止x*x溢出
    if (n & 1) res = res * x % mod;
    return res;
}

素数的性质

素性测试

所谓素数，是指恰好有两个公约数的整数。因为n的约数都不超过n，所以只要检查2～n-1的所有整数是否能够整除n就能判定n是不是素数。如果d是n的约数。由n=d * n/d可知$min(d, n/d) \leq \sqrt n$

1
2
3
4
5
6
bool test_prime(int n){ 
        for (int i = 1; i * i <= n; i++){
                if (n % i == 0) return false;
        }
        return n != 1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
//约数枚举,约数个数
vector<int> divisor(int n){ 
        vector<int> res;

        for(int i = 1; i * i <= n; i++){
                if (n % i == 0){ 
                        res.push_back(i);
                        if (i != n/i) res.push_back(n/i);
        printf("\n");
                }
        }
        return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
//这个数除约数的个数
map<int, int> prime_factor(int n){
        map<int, int> res;
        for(int i = 2; i * i < n; i++){
                while(n % i == 0){
                        ++res[i];
                        n/=i;
                }
        }
        if ( n != 1) res[n] = 1;
        return res;
}

素数个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//某个数以内素数的个数

const int MAX_N = 100000;
int prime[MAX_N];    //依次记录素数，数组的size反应了素数的个数
bool is_prime[MAX_N];

int sieve(int n){
        int p = 0;
        for(int i = 0; i <= n; i++){
                is_prime[i] = true;
        }
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i <= n; i++){
                if (is_prime[i]){
                        for(int j = 2*i; j <= n; j+=i){
                                is_prime[j] = false;
                        }
                        prime[p++] = i;
                }
        }
        return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//某个区间内素数的个数
typedef long long ll;
const int MAX_L = 1000000;
const int MAX_SORT_B = 1000000;

bool is_prime1[MAX_L];      //存储的是[a,b)
bool is_prime_small[MAX_SORT_B];    //存储的是[2,sqrtb)

// 对区间[a,b)执行筛选，is_prime1[i-a] == true表明i是素数
int segment_sieve(ll a, ll b){
        for(int i = 0; (ll)i * i < b; i++)  is_prime_small[i] = true;
        is_prime_small[0] = is_prime_small[1] = false;

        for(int i = 0; i < b-a; i++) is_prime1[i] = true;

        for(int i = 2; (ll) i * i < b; i++){
                if (is_prime_small[i]){
                        for(int j = 2 *i; (ll)j*j< b; j += i )
                                is_prime_small[j] = false;
                                
                        //求出位于区间[a, b)的最小的i的倍数
                        /*
                        ll num = (ll)2*i;
                        while(num < a){
                                num += i;
                        }
                        for (int j = num; j < b; j+=i){
                                is_prime1[j-a] = false;
                        }*/
                        //求出位于区间[a, b)的最小的i的倍数
                        for(ll j = max(2LL, (a+i-1) / i) * i; j < b; j += i){
                                is_prime1[j - a] = false;
                        }

                }
        }
        int count = 0;
        for (int i = 0; i < (int)(b-a); i++){
                if(is_prime1[i])
                        count++;
        }
        return count; 
}