模版:约数

约数（一个数的约数包括 1 及其本身）

如果 N = p1^c1 * p2^c2 * ... *pk^ck

（1）试除法求一个数的所有约数（）
另外更快的方法：预处理1到的质因子，通过dfs拼接出所有的约数（具体题目）

对于枚举b1的所有约数，即for(int i = 1;i <= b1 / i;i ++),此操作的复杂度是，可以先预处理出 的所有约数，再枚举约数，而不需要从1开始枚举到 ，预处理 的所有约数的方法是筛出1到的所有质因子，特别地，若 是一个质数，也需要筛出来，再通过dfs把所有约数都找出来

（2）约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
（3）约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
（4）欧几里得算法
（5）1到N中，所有数的约数的个数之和（注意：这里是n个数，不是1个数，n！是一个数）：
（6）0<= N <= 2 ^31 - 1中，这个范围的约数个数最多的数的约数个数有1600个
（7）2 * 3 * 5 * 7 ... * 23 < 2 * 10^9，而2 * 3 * 5 * 7 ... * 23 * 29 > 2 * 10^9，因此在2 * 10^9之内用到的质数乘积只会用到23
2^30 = 1,073,741,824 < 2 * 10^9 且2^31 > 2 * 10^9
（8）大概是

1、试除法求一个数的所有约数

上面代码只会循环到 ，时间复杂度是 ，M 是约数个数。
注意：必须从1开始枚举，1和该数本身也是它的约数

public static List<Integer> get_divisors(int x)
    {
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 1;i <= x/ i;i++)
        {
            if(x % i == 0) 
            {
                list.add(i);
                if(i != x / i) list.add(x / i);
            }
        }
        Collections.sort(list);
        return list;
    }

2、约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)

给定n个正整数ai，请你输出这些数的乘积的约数个数，答案对10^9+7取模。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static int mod = 1000000007;
    static Map<Integer,Integer> primes = new HashMap<Integer,Integer>();
    public static void get_primes(int x)
    {
        for(int i = 2;i <= x/i;i++)
        {
            while(x % i == 0)
            {
                primes.put(i, primes.getOrDefault(i, 0) + 1);
                x /= i;
            }
        }
        if(x > 1) primes.put(x, primes.getOrDefault(x, 0) + 1);
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        while(n -- > 0)
        {
            int x =scan.nextInt();
            get_primes(x);
        }
        long res = 1;
        for(Map.Entry<Integer, Integer> entry : primes.entrySet())
        {
            res = res * (entry.getValue() + 1) % mod;
        }
        System.out.println(res);
    }

}

3、约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

给定n个正整数ai，请你输出这些数的乘积的约数之和，答案对10^9+7取模。
解析：
若求1 + p^1 + p^2 + p^3... + p^k,可以通过迭代的方式求解t = t * p + 1
1 = 0 * p + 1;
1 + p ^1 = 1 * p + 1
1 + p^1 + p^2 = (1 + p ^1) * t + 1
....

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static int mod = 1000000007;
    static Map<Integer,Integer> primes = new HashMap<Integer,Integer>();
    public static void get_primes(int x)
    {
        for(int i = 2;i <= x/i;i++)
        {
            while(x % i == 0)
            {
                primes.put(i, primes.getOrDefault(i, 0) + 1);
                x /= i;
            }
        }
        if(x > 1) primes.put(x, primes.getOrDefault(x, 0) + 1);
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        while(n -- > 0)
        {
            int x =scan.nextInt();
            get_primes(x);
        }
        long res = 1;
        for(Map.Entry<Integer, Integer> entry : primes.entrySet())
        {
            long t = 1;
            int a = entry.getKey();
            int b = entry.getValue();
            while(b -- > 0) t = (t * a + 1) % mod;
            res =  (res * t) % mod;
        }
        System.out.println(res);
    }

}

4、欧几里得算法

推导：
若d能整除a，d能整除b ，则d一定能整除(ax + by)
例如，3能整除12,3能整除6，则3一定能整除(12x + 6y)
由于 a mod b = a - (a/b) * b = a - c * b
因此假设a和b的最大公约数为 x，则x能整除a，x能整除b，因此，x一定能整除a - c * b，则gcd(a,b) == gcd(b,a - c * b)

public static int gcd(int a,int b)
{
        return b == 0 ? a : gcd(b,a % b);
}

扩展：

阶乘分解

题目描述

给定整数 N ，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。

输入格式
一个整数N。

输出格式
N! 分解质因数后的结果，共若干行，每行一对pi,ci，表示含有pcii项。按照pi从小到大的顺序输出。

数据范围
1≤N≤106
输入样例：
5
输出样例：
2 3
3 1
5 1
样例解释
5!=120=2^3∗3∗5

算法分析

• 1、筛出1~10^6的所有质数
• 2、枚举每个质因子P，n!表示1 * 2 * 3... * n,从1到n中，求P的次数：(一共有项)
  • P的倍数有个
  • P^2的倍数有个
  • P^3的倍数有个
  • ...

时间复杂度

有个质数，每个质数求次，因此时间复杂度是级别

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);
        }
    }
}

5、裴蜀定理

若a，b是整数，且gcd(a,b) = d，那么对于任意的整数x，y，ax + by 都一定是d的倍数。特别地，一次存在非零整数x，y，使得ax + by = d成立

6、扩展欧几里得

扩展欧几里得找的是裴蜀定理中：一次存在非零整数x，y，使得ax + by = d成立，找到里面的x和y的一组解

当算出一组解x0,y0时，如何求出x和y的通项

则，

其中x的最小解是

给定n对正整数ai,bi，对于每对数，求出一组xi,yi，使其满足ai∗xi+bi∗yi=gcd(ai,bi)。

输入格式
第一行包含整数n。

接下来n行，每行包含两个整数ai,bi。

输出格式
输出共n行，对于每组ai,bi，求出一组满足条件的xi,yi，每组结果占一行。

本题答案不唯一，输出任意满足条件的xi,yi均可。

Java 代码

import java.util.Scanner;
public class Main
{
    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] -= a / b * x[0];
        return d;
    }
    public static void main(String[] args) {
         Scanner scan = new Scanner(System.in);
         int n = scan.nextInt();
         while(n -- > 0)
         {
             int a = scan.nextInt();
             int b = scan.nextInt();
             int[] x = new int[1];
             int[] y = new int[1];
             exgcd(a,b,x,y);
             System.out.println(x[0] + " " + y[0]);
         }
    }
}