亚洲男女激情,蜜臀熟女AV在线

質(zhì)數(shù)：在大于1的整數(shù)中，如果只包含1和本身這兩個約數(shù)，則稱該數(shù)為質(zhì)數(shù)或者素?cái)?shù)

（1）判斷質(zhì)數(shù)（試除法）
（2）分解質(zhì)因素（試除法）
（3）求1~n中所有的質(zhì)數(shù)
（4）階乘分解

1、判斷質(zhì)數(shù)（試除法） $O( \sqrt n)$

（1）從定義出發(fā)判斷是否質(zhì)數(shù)

時間復(fù)雜度O（n）

    static boolean is_primes(int x)
    {
        if(x < 2) return false;
        for(int i = 2;i <= x;i ++)
        {
            if(x % i == 0) return false;
        }
        return true;
    }

（2）從整除角度出發(fā)判斷是否質(zhì)數(shù)
定理：n中最多只包含一個大于 $\sqrt n$ 的質(zhì)數(shù)

時間復(fù)雜度 $O( \sqrt n)$

若d能整除n，則d/n 也能整除n，例如 2能整除12 ，則6也能整除12
從小到大枚舉到 min（d,n/d）,不妨設(shè)d <= n/d,則d^2 <= n

    static boolean is_primes(int x)
    {
        if(x < 2) return false;
        for(int i = 2;i <= x / i;i ++)
        {
            if(x % i == 0) return false;
        }
        return true;
    }

2、分解質(zhì)因素（試除法） $O( \sqrt n)$

public static void divide(int x)
    {
        for(int i = 2;i <= x / i;i++)
        {
            if(x % i == 0)
            {
                int s = 0;
                while(x % i == 0)
                {
                    s ++;
                    x /= i;
                }
                System.out.println(i + " " + s);
            }
        }
        if(x > 1) System.out.println(x + " " + 1);
        System.out.println();
    }

3、求1~n中所有的質(zhì)數(shù)

（1）樸素篩法 $O(nlogn)$
原理：任意整數(shù)x的倍數(shù)2x,3x,...都不是質(zhì)數(shù)
由于每次篩選的個數(shù)的累加是
(n/2 + n/3 + n/4 +... + n/n) = n(1 + 1/2 + 1/3 +...+ 1/n) = nlnn

image.png

static int N = 1000000;
    static int[] primes = new int[N];
    static boolean[] st = new boolean[N];
    static int cnt = 0;//記錄質(zhì)數(shù)的個數(shù)
    public static void get_primes(int n)
    {
        for(int i = 2;i <= n;i++)
        {
            if(!st[i])
            {
                primes[cnt ++] = i;
            }
            for(int j = i * 2;j <= n;j += i)
                st[j] = true;
        }
    }

（2）埃氏篩法 $O(nloglogn)$

只需把質(zhì)數(shù)的倍數(shù)篩掉即可

從1到n中一共有n/(lnn)個質(zhì)數(shù)
每次篩選的個數(shù)的累加是
(n/2 + n/3 + n/5 + n/7 + n/11 +...+ 1/n) = $O(nloglogn)$

    static int N = 1000000;
    static int[] primes = new int[N];
    static boolean[] st = new boolean[N];
    static int cnt = 0;//記錄質(zhì)數(shù)的個數(shù)
    public static void get_primes(int n)
    {
        for(int i = 2;i <= n;i++)
        {
            if(!st[i])
            {
                primes[cnt ++] = i;
                for(int j = i * 2;j <= n;j += i)
                    st[j] = true;
            }
        }
    }

（2）線性篩法 $O(n)$
原理：每個合數(shù)i * p只會被它的最小質(zhì)因子p篩一次

1、i % primes[j] == 0
primes[j]一定是i的最小質(zhì)因子，primes[j]一定是primes[j] * i的最小質(zhì)因數(shù)
2、i % primes[j] != 0
primes[j] 一定小于i的所有質(zhì)因子，primes[j]一定是primes[j] * i的最小質(zhì)因數(shù)
注意：在 2 操作中，若滿足則必須停下，否則j ++ 時，后面的i * primes[j] 的最小質(zhì)因子不是primes[j]

注意：篩[0,n]區(qū)間內(nèi)的質(zhì)數(shù)和篩[0,n)區(qū)間內(nèi)的質(zhì)數(shù)的區(qū)別在于這行代碼for (int j = 0; i * primes.get(j) < n; j++) ，若i * primes.get(j) <= n，則就篩[0,n]的所有質(zhì)數(shù),也可以寫成primes.get(j) <= n / i;i * primes.get(j) < n，則篩[0,n]的所有質(zhì)數(shù)

    static int N = 1000010;
    static boolean[] st = new boolean[N];//st[x]存儲x是否被篩掉
    static int cnt = 0;
    static int[] primes = new int[N];//primes[]存儲所有素?cái)?shù)
    public static void get_primes(int x)
    {
        for(int i = 2;i <= x ;i++)
        {
            if(!st[i]) primes[cnt ++] = i;
            for(int j = 0;primes[j] <= x / i;j++)
            {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) break;//primes[j]一定是i的最小質(zhì)因子
            }
        }
    }

4、階乘分解

算法分析

1、篩出1~10^6的所有質(zhì)數(shù)
2、枚舉每個質(zhì)因子P，n!表示1 * 2 * 3... * n,從1到n中，求P的次數(shù)：(一共有項(xiàng))
- P的倍數(shù)有 $\lfloor \frac{n}{p} \rfloor$ 個
- P^2的倍數(shù)有 $\lfloor \frac{n}{p^2} \rfloor$ 個
- P^3的倍數(shù)有 $\lfloor \frac{n}{p^3} \rfloor$ 個
- ...

時間復(fù)雜度 $O(n)$

有 $\frac{n}{lnn}$ 個質(zhì)數(shù)，每個質(zhì)數(shù)求 $log_{p}n$ 次，因此時間復(fù)雜度是 $O(n)$ 級別

Java 代碼

import java.util.Scanner;

public class Main {
    static int N = 1000010; 
    static boolean[] st = new boolean[N];
    static int[] primes = new int[N];
    static int cnt = 0;
    static void init(int n)
    {
        for(int i = 2;i <= n;i ++)
        {
            if(!st[i]) primes[cnt ++] = i;
            for(int j = 0;primes[j] * i <= n;j ++)
            {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) break;
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        init(n);
        for(int i = 0;i < cnt;i ++)
        {
            int p = primes[i],s = 0;
            for(int j = n;j != 0;j /= p)
            {
                s += j / p;
            }
            System.out.println(p + " " + s);
        }
    }
}

快速冪

&是二進(jìn)制的“與”運(yùn)算
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 0
3 & 2 = 0111 & 0010 = 0010 = 2

x & 1 的結(jié)果就是取二進(jìn)制的最末位
x & 1 == 0 , 則 x 為偶數(shù)
x & 1 == 1 , 則 x 為奇數(shù)

>> 運(yùn)算比較單純，二進(jìn)制去掉最后一位

image.png

public static long qmi(int a,int k,int p)
    {
        long res = 1 % p;
        long t = a;
        while(k > 0)
        {
            if((k & 1) == 1) res = res * t % p;
            k >>= 1;
            t = t * t % p;
        }
        return res;
    }

快速冪求逆元

引理：

image.png

證明分析：
費(fèi)馬小定理的推導(dǎo)來自楊輝三角形，在楊輝三角形中，可以發(fā)現(xiàn)每一行都是

(x + 1) ^ n

的展開式的系數(shù)，當(dāng)n為任意質(zhì)數(shù)p時，因?yàn)樵谡归_過程中沒有被約分過，因此展開式中的系數(shù)除了第一項(xiàng)和最后一項(xiàng)，其余全是p的倍數(shù)，
因此當(dāng)p為質(zhì)數(shù)時，

(n + 1)^p - n^p - 1

一定是質(zhì)數(shù)p的倍數(shù)
由于下列方程一定成立

(n ^ p - n) + [(n + 1)^p - n^p - 1] = (n + 1)^p - (n + 1)

由于第二大項(xiàng)一定是質(zhì)數(shù)p的倍數(shù)，對于這個式子的某個命題，第n項(xiàng)成立，則第

n + 1

項(xiàng)也成立，因此
當(dāng)

n = 1

時，

n^p - n = 1 - 1 = 0

0

可以被任意質(zhì)數(shù)整除，
由數(shù)學(xué)歸納法，費(fèi)馬小定理證畢。

image.png

給定n組ai,pi，其中pi是質(zhì)數(shù),求ai模pi的乘法逆元，若逆元不存在則輸出impossible。

import java.util.Scanner;

public class Main {
    public static long qmi(int a,int k,int p)
    {
        long res = 1 % p;
        long t = a;
        while(k > 0)
        {
            if((k & 1) == 1) res = res * t % p;
            k >>= 1;
            t = t * t % p;
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        while(n -- > 0)
        {
            int a = scan.nextInt();
            int p = scan.nextInt();
            long t = qmi(a,p - 2,p);
            if(a % p == 0) System.out.println("impossible");//若a是p的倍數(shù)，則一定無解
            else System.out.println(t);
        }
    }
}

龜速乘法

算法分析

快速冪與龜速乘法的對比
快速冪解決 $a ^ b$ $mod$ $p$ 的問題，而龜速乘法解決 $a * b$ $mod$ $p$ 的問題

本質(zhì)上
快速冪： $a ^ b$ $mod$ $p$ $= a * a * a ... * a % p$
龜速乘： $a * b$ $mod$ $p$ $= a + a + a ... + a % p$

快速冪：從 $a$ 算出 $a^2$ , 再算出 $a^4$ ， $a^8$ ...(通過 $k$ 的二進(jìn)制中哪些位需要加上該位的值，算出 $a^k$ )
龜速乘：從 $a$ 算出 $2 * a$ , 再算出 $4 * a$ ， $8 * a$ ...(通過 $k$ 的二進(jìn)制中哪些位需要加上該位的值，算出 $a * k$ )

注意:Java 的同學(xué)還可以直接使用BigInteger算很大的值

時間復(fù)雜度 $O(logb)$

參考文獻(xiàn)

算法提高課

Java 代碼(龜速乘)

import java.util.Scanner;

public class Main {
    static long qadd(long a,long k,long p)
    {
        long res = 0;
        while(k > 0)
        {
            if((k & 1) == 1) res = (res + a) % p;
            k >>= 1;
            a = (a + a) % p;
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long a = scan.nextLong();
        long b = scan.nextLong();
        long p = scan.nextLong();
        System.out.println(qadd(a,b,p));
    }
}

Java 代碼(BigInteger)

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        BigInteger a = new BigInteger(scan.next());
        BigInteger b = new BigInteger(scan.next());
        BigInteger p = new BigInteger(scan.next());
        System.out.println(a.multiply(b).mod(p));
    }
}

擴(kuò)展歐幾里得

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int x;
    static int y;
    public static int exgcd(int a,int b,int[] x,int[] y)
    {
        if(b == 0)
        {
            x[0] = 1;
            y[0] = 0;
            return a;
        }
        int d = exgcd(b,a % b,y,x);
        y[0] = y[0] - a/b * x[0];
        return d;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        int[] x = new int[1];
        int[] y = new int[1];
        while(n -- > 0)
        {
            String[] s1 = reader.readLine().split(" ");
            int a = Integer.parseInt(s1[0]);
            int b = Integer.parseInt(s1[1]);
            exgcd(a,b,x,y);
            System.out.println(x[0] + " " + y[0]);
        }
    }

}

image.png

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

模版:數(shù)學(xué)知識(1)

模版:數(shù)學(xué)知識(1)

質(zhì)數(shù)：在大于1的整數(shù)中，如果只包含1和本身這兩個約數(shù)，則稱該數(shù)為質(zhì)數(shù)或者素?cái)?shù)

1、判斷質(zhì)數(shù)（試除法） $O( \sqrt n)$

時間復(fù)雜度O（n）

時間復(fù)雜度 $O( \sqrt n)$

2、分解質(zhì)因素（試除法） $O( \sqrt n)$

3、求1~n中所有的質(zhì)數(shù)

只需把質(zhì)數(shù)的倍數(shù)篩掉即可

4、階乘分解

算法分析

時間復(fù)雜度 $O(n)$

Java 代碼

快速冪

快速冪求逆元

引理：

龜速乘法

算法分析

時間復(fù)雜度 $O(logb)$

參考文獻(xiàn)

Java 代碼(龜速乘)

Java 代碼(BigInteger)

擴(kuò)展歐幾里得

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

模版:數(shù)學(xué)知識(1)

質(zhì)數(shù)：在大于1的整數(shù)中，如果只包含1和本身這兩個約數(shù)，則稱該數(shù)為質(zhì)數(shù)或者素?cái)?shù)

1、判斷質(zhì)數(shù)（試除法）

時間復(fù)雜度O（n）

時間復(fù)雜度

2、分解質(zhì)因素（試除法）

3、求1~n中所有的質(zhì)數(shù)

只需把質(zhì)數(shù)的倍數(shù)篩掉即可

4、階乘分解

算法分析

時間復(fù)雜度

Java 代碼

快速冪

快速冪求逆元

引理：

龜速乘法

算法分析

時間復(fù)雜度

參考文獻(xiàn)

Java 代碼(龜速乘)

Java 代碼(BigInteger)

擴(kuò)展歐幾里得

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

質(zhì)數(shù)：在大于1的整數(shù)中，如果只包含1和本身這兩個約數(shù)，則稱該數(shù)為質(zhì)數(shù)或者素?cái)?shù)

1、判斷質(zhì)數(shù)（試除法） $O( \sqrt n)$

時間復(fù)雜度 $O( \sqrt n)$

2、分解質(zhì)因素（試除法） $O( \sqrt n)$

3、求1~n中所有的質(zhì)數(shù)

4、階乘分解

時間復(fù)雜度 $O(n)$

時間復(fù)雜度 $O(logb)$