约数（一个数的约数包括 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的一组解
image.png
当算出一组解x0,y0时，如何求出x和y的通项
则，
其中x的最小解是
image.png
image.png
image.png
给定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]);
}
}
}
网友评论