约数相关算法主要内容
一、基本思路1、定义2、试除法——求一个数的所有约数3、约数个数4、约数之和5、欧几里得算法——辗转相除法（求解最大公约数）
二、Java、C语言模板实现三、例题题解
一、基本思路
1、定义
约数：
约数是指一个数（因数）能整除另一个数的正整数，也称为因数。 举例：
“||”表示整除，a||b,即为 a 整除 b ，则，b/a为一个整数。
2、试除法——求一个数的所有约数
(d || n) ==> (n/d || n) ==> (d <= n/d) ==> (d <= sqrt(n))其中 d 与 n/d 都是 n 的约数，并且成对出现，我们需要成对储存但是需要特判一种情况—— i ?= n/i
3、约数个数
质因数（正整数）分解定理： 约数个数定理： 问题：是否可以用试除法求解约数个数？
理论上暴力求解可以，但是稍微大一点的数就会极容易溢出。
4、约数之和
约数之和定理： 求解技巧：
5、欧几里得算法——辗转相除法（求解最大公约数）
基本性质：
(d||a ， d||b) ⇒ (d||ax+by); 核心原理：
(a, b)代表求解 a，b的最大公约数
(a, b) = (b , a mod b) 欧几里得算法原理证明：
二、Java、C语言模板实现
// java 模板
// 1、试错法求解约数
static void getDiv(int n){
PriorityQueue
// 优先队列，Integer已经实现了Comparable接口，可以实现自动排序
int count = 0;
for(int i = 1; i <= n/i; i++){ // i 与 n/i 成对存在，能成为n的约数，那么n/i也可以是
if(n % i == 0){ // 满足整除条件，则为约数
q.add(i);
count++;
if(i != n/i){ // 如果满足条件，那么就是与之对应的另一对约数，不满足则重复了
q.add(n/i);
count++;
}
}
}
for(int i = 0; i < count; i++){
System.out.print(q.poll() + " ");
}
}
// 2、约数个数求解
for(int ii = 0; ii < n; ii++){
int x = Integer.parseInt(reader.readLine());
// 此处使用的是分解质因数的模板，得到的每个数的质因数以及指数
for(int i = 2; i <= x/i; i ++){
while(x % i == 0){
x /= i;
map.put(i, map.getOrDefault(i, 0) + 1);
}
}
if(x > 1){
map.put(x, map.getOrDefault(x, 0) + 1);
}
}
long res = 1;
for(int value : map.values()){
res = res * (value + 1) % Mod;
/ 此处一边相乘，一边mod，是因为一旦数字变大，就会导致溢出，影响最后的结果
}
// 3、约数之和求解
for(int ii = 0; ii < n; ii++){
int x = Integer.parseInt(reader.readLine());
// 此处使用的是分解质因数的模板，得到的每个数的质因数以及指数
for(int i = 2; i <= x/i; i ++){
while(x % i == 0){
x /= i;
map.put(i, map.getOrDefault(i, 0) + 1);
}
}
if(x > 1){
map.put(x, map.getOrDefault(x, 0) + 1);
}
// map 中存储的是键值对————质因数pi与质数ai
long res = 1;
for(int key : map.keySet()){
long t = 1;
int value = map.get(key);
while(value-- > 0){
t = (t * key + 1) % Mod; // 进行取模运算是为了防止溢出
}
// 此处模仿了 p^0 + p^1 +...+p^a
// t = 1;
// t = p + 1;
// t = p^2 + p + 1;
// t = p^3 + p^2 + p + 1;
res = res*t % Mod;
}
// 4、最大公约数————欧几里得算法
static int gcd(int a, int b){
// 用到了递归思想 + 欧几里得算法公式
return b != 0 ? gcd(b, a % b) : a; // 应该是b不等0的时候呀，满足第一个表达式，等于0满足第二个表达式
}
// C++ 模板，由yxc实现
// 1、试错法求解约数
试除法求所有约数 —— 模板题 AcWing 869. 试除法求约数
vector
{
vector
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
// 2、约数个数求解 约数之和求解
约数个数和约数之和 —— 模板题 AcWing 870. 约数个数, AcWing 871. 约数之和
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
// 3、最大公约数————欧几里得算法
欧几里得算法 —— 模板题 AcWing 872. 最大公约数
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
三、例题题解
// java题解实现
import java.util.*;
public class Main{
static void getDiv(int n){
PriorityQueue
// 优先队列，Integer已经实现了Comparable接口，可以实现自动排序
int count = 0;
for(int i = 1; i <= n/i; i++){ // i 与 n/i 成对存在，能成为n的约数，那么n/i也可以是
if(n % i == 0){ // 满足整除条件，则为约数
q.add(i);
count++;
if(i != n/i){ // 如果满足条件，那么就是与之对应的另一对约数，不满足则重复了
q.add(n/i);
count++;
}
}
}
for(int i = 0; i < count; i++){
System.out.print(q.poll() + " ");
}
System.out.println();
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for(int i = 0; i < n; i++){
int ai = in.nextInt();
getDiv(ai);
}
}
}
import java.util.*;
import java.io.*;
public class Main{
static long Mod = (long)1e9 + 7;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
HashMap
// 用HashMap是因为键值key是唯一的，也就意味着我们先将每个数分解成质因数和指数形式即可
// 因为质因数分解和本题中的各个数之间关系都是相乘
// 因此在相同key的对应的不同指数就含有了不同数相乘信息
int n = Integer.parseInt(reader.readLine());
for(int ii = 0; ii < n; ii++){
int x = Integer.parseInt(reader.readLine());
// 此处使用的是分解质因数的模板，得到的每个数的质因数以及指数
for(int i = 2; i <= x/i; i ++){
while(x % i == 0){
x /= i;
map.put(i, map.getOrDefault(i, 0) + 1);
}
}
if(x > 1){
map.put(x, map.getOrDefault(x, 0) + 1);
}
}
long res = 1;
for(int value : map.values()){
res = res * (value + 1) % Mod;
// 此处一边相乘，一边mod，是因为一旦数字变大，就会导致溢出，影响最后的结果
}
System.out.println(res);
}
}
import java.util.*;
import java.io.*;
public class Main{
static long Mod = (long)1e9 + 7;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
HashMap
// 用HashMap是因为键值key是唯一的，也就意味着我们先将每个数分解成质因数和指数形式即可
// 因为质因数分解和本题中的各个数之间关系都是相乘
// 因此在相同key的对应的不同指数就含有了不同数相乘信息
int n = Integer.parseInt(reader.readLine());
for(int ii = 0; ii < n; ii++){
int x = Integer.parseInt(reader.readLine());
// 此处使用的是分解质因数的模板，得到的每个数的质因数以及指数
for(int i = 2; i <= x/i; i ++){
while(x % i == 0){
x /= i;
map.put(i, map.getOrDefault(i, 0) + 1);
}
}
if(x > 1){
map.put(x, map.getOrDefault(x, 0) + 1);
}
}
// map 中存储的是键值对————质因数pi与质数ai
long res = 1;
for(int key : map.keySet()){
long t = 1;
int value = map.get(key);
while(value-- > 0){
t = (t * key + 1) % Mod; // 进行取模运算是为了防止溢出
}
// 此处模仿了 p^0 + p^1 +...+p^a
// t = 1;
// t = p + 1;
// t = p^2 + p + 1;
// t = p^3 + p^2 + p + 1;
res = res*t % Mod;
}
System.out.println(res);
}
}
import java.util.*;
import java.io.*;
public class Main{
static int gcd(int a, int b){
// 用到了递归思想 + 欧几里得算法公式
return b != 0 ? gcd(b, a % b) : a; // 应该是b不等0的时候呀，满足第一个表达式，等于0满足第二个表达式
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
for(int i = 0; i < n; i++){
String[] str = in.readLine().split(" ");
int a = Integer.parseInt(str[0]);
int b = Integer.parseInt(str[1]);
System.out.println(gcd(a, b));
}
}
}