判断一个数的所有约数
求一个数的约数个数
求一个数的约数之和
求两个数最大公约数
求两个数最小公倍数
AcWing 869. 试除法求约数 原题链接
给定n个正整数aiai，对于每个整数aiai,请你按照从小到大的顺序输出它的所有约数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个整数aiai。
输出格式
输出共n行，其中第 i 行输出第 i 个整数aiai的所有约数。
数据范围
1≤n≤1001≤n≤100, 2≤ai≤2∗1092≤ai≤2∗109
输入样例：
2
6
8
输出样例：
1 2 3 6
1 2 4 8
static int[] divisor;
static int count;
public static void main(String[] args) {
int n = in.nextInt();
divisor = new int[800_0000];
while (n-- > 0) {
count = 0;
approximate(in.nextInt());
Arrays.sort(divisor, 0, count);
for (int i = 0; i < count; i++) {
out.print(divisor[i] + " ");
}
out.println();
}
out.flush();
out.close();
}
private static void approximate(int x) {
for (int i = 1; i <= x / i; i++) {
if (x % i == 0) {
divisor[count++] = i;
if (i != x / i) {
divisor[count++] = x / i;
}
}
}
}
AcWing 870. 约数个数 原题链接
给定n个正整数aiai，请你输出这些数的乘积的约数个数，答案对109+7109+7取模。
输入格式
第一行包含整数n。
接下来n行，每行包含一个整数aiai。
输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对109+7109+7取模。
数据范围
1≤n≤1001≤n≤100, 1≤ai≤2∗1091≤ai≤2∗109
输入样例：
3
2
6
8
输出样例：
12
static int mod = (int) (1e9 + 7);
static Map<Integer, Integer> map = new HashMap<>();
public static void sum(int x) {
//先进行质因数 分解
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
int s = 0;
while (x % i == 0) {
s++;
x /= i;
}
map.put(i, map.getOrDefault(i, 0) + s);
}
}
if (x > 1) {
map.put(x, map.getOrDefault(x, 0) + 1);
}
}
public static void main(String[] args) {
int n = in.nextInt();
long res = 1L;
while (n-- > 0) {
sum(in.nextInt());
}
Collection<Integer> values = map.values();
for (Integer v : values) {
res = (res * (v + 1)) % mod;
}
out.println(res);
out.flush();
out.close();
}
AcWing 871. 约数之和 原题链接
给定n个正整数aiai，请你输出这些数的乘积的约数之和，答案对109+7109+7取模。
输入格式
第一行包含整数n。
接下来n行，每行包含一个整数aiai。
输出格式
输出一个整数，表示所给正整数的乘积的约数之和，答案需对109+7109+7取模。
数据范围
1≤n≤1001≤n≤100, 1≤ai≤2∗1091≤ai≤2∗109
输入样例：
3
2
6
8
输出样例：
252
static int mod = (int) (1e9 + 7);
static Map<Integer, Integer> map = new HashMap<>();
public static void sum(int x) {
//先进行质因数 分解
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
int s = 0;
while (x % i == 0) {
s++;
x /= i;
}
map.put(i, map.getOrDefault(i, 0) + s);
}
}
if (x > 1) {
map.put(x, map.getOrDefault(x, 0) + 1);
}
}
public static void main(String[] args) {
int n = in.nextInt();
long res = 1L;
while (n-- > 0) {
sum(in.nextInt());
}
Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
for (Map.Entry<Integer, Integer> e : entries) {
int p = e.getKey();
int mul = e.getValue();
long t = 0L;
for (int i = 0; i <= mul; i++) {
t = (t * p + 1) % mod;
}
res = res * t % mod;
}
out.println(res);
out.flush();
out.close();
}
AcWing 872. 最大公约数 原题链接
给定n对正整数ai,biai,bi，请你求出每对数的最大公约数。
输入格式
第一行包含整数n。
接下来n行，每行包含一个整数对ai,biai,bi。
输出格式
输出共n行，每行输出一个整数对的最大公约数。
数据范围
1≤n≤1051≤n≤105, 1≤ai,bi≤2∗1091≤ai,bi≤2∗109
输入样例：
2
3 6
4 6
输出样例：
3
2
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}