1、約數：

1.1 試除法求約數

原理：只需要遍歷最小的約數即可，較大的那個可以直接算出來。

import java.util.*;
public class Main {static Scanner sc = new Scanner(System.in);public static void main(String[] args) {int t = sc.nextInt();while(t-- > 0){solution();System.out.println();}}public static void solution(){int n = sc.nextInt();Set<Integer> set = new TreeSet<>(Integer::compare);for(int i = 1;i <= n / i;i++) {if(n % i == 0) {set.add(i);set.add(n / i);}}set.forEach((l)-> System.out.print(l + " "));}
}

1.2 求約數的個數

原理：

任何一個數 x 都可以寫成為：x = q₁^a1 + q₂^a2 + … + q_n^ak

因此：約數個數的公式為：

count = (a₁ + 1) × (a₂ + 1) × … × (a_k + 1)

同理：約數的和的公式為：

sum = (q₁⁰ + q₁¹ + q₁² + … + q₁^a1) × (q₂⁰+ q₂¹ + q₂² + … + q₂^a2) × … × (q_n⁰ + q_n¹ + … + q_n^ak)

例如：12 = 2² + 3¹

約數個數為：(2 + 1)× (1 + 1) = 2 × 3 = 6

驗證：12 的約數有 1、2、3、4、6、12 一共 六 個

約數和為：(2⁰ + 2¹ + 2²) × (3⁰ + 3¹) = 28

驗證：1 + 2 + 3 + 4 + 6 + 12 = 28

import java.util.*;public class Main{static int N = (int) (1e9+7);public static void main(String[] args){Scanner sc = new Scanner(System.in);// 利用hash表存儲這個數的因數以及指數 x = q1a1 + q2a2 + ... + qnak Map<Integer,Integer> map = new HashMap<>();int n = sc.nextInt();while(n-- > 0) {int x = sc.nextInt();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) // 如果 x > 1，表示這個數沒有被除進，直接將這個數放進去就好map.put(x,map.getOrDefault(x,0)+1);}long res = 1;// 這些乘積的結果的 約數的個數為 指數 + 1的乘積Set<Map.Entry<Integer, Integer>> entries = map.entrySet();for(Map.Entry<Integer, Integer> e : entries) {res = res * (e.getValue() + 1) % N;}System.out.println(res);}
}

import java.util.*;public class Main{static int N = (int) (1e9+7);public static void main(String[] args){Scanner sc = new Scanner(System.in);// 利用hash表存儲這個數的因數以及指數Map<Integer,Integer> map = new HashMap<>();int n = sc.nextInt();while(n-- > 0) {int x = sc.nextInt();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) // 如果 x > 1，表示這個數沒有被除進，直接將這個數放進去就好map.put(x,map.getOrDefault(x,0)+1);}long res = 1;// 這些乘積的結果的 約數的個數為 指數 + 1的乘積Set<Map.Entry<Integer, Integer>> entries = map.entrySet();for(Map.Entry<Integer, Integer> e : entries) {long t = 1;int p = e.getKey();int a = e.getValue();// 這里就是算(q1^0 + q2^1 + q3^2 + ... + qn^a1)while(a -- > 0)  t = (t * p + 1) % N;res = res * t % N;}System.out.println(res);}
}

1.3 最大公因數（最大公約數）

原理：根據 (a,b) = (a,R) ===> 表示，a 和 b的共因數等于a和a % b的公因數

import java.util.*;
public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();while(n-- > 0) {int a = sc.nextInt();int b = sc.nextInt();System.out.println(gcd(a,b));}}static int gcd(int a,int b) {// 關鍵點：// 如果 a > b 那末就是想要的，b a換位，并且用小的取余大的// 如果 a < b 那末，由于 a%b=a 因此，相當于換位，值不變return b == 0 ? a : gcd(b,a%b);}
}