约数之和

题目描述

假设现在有两个自然数 $A, B$，$S$ 是这两个数的所有约数之和。

请你求出 $S \%9901$ 的值是多少。

输入格式

在一行中输入用空格隔开的两个整数 $A, B$。

输出格式

输出一个整数，代表 $S \%9901$ 的值。

数据范围

两数均在 $5e7$ 范围内

输入样例：

1
2 3

输出样例：

1
15

注意: 两数不会同时为 0。

分析求解

约数和公式

对于任意正整数 $N$,可以表示为若干素因数的乘积

这些约数个总个数为

这些约数的和

把 A 分解质因数，进而就可以把 A 的 B 次方分解质因数，然后带入第三个式子求解即可

第三个式子是一个等比数列求和然后求积的形式，可以通过公式或者分治办法来求

代码如下：（此题涉及了很多模板，需要自取）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int max(int... a) {
		int res = 0, n = a.length;
		if (n == 2) return Math.max(a[0], a[1]);
		for (int x : a) res = Math.max(res, x);
		return res;
	}
	
	static int min(int... a) {
		int res = 0, n = a.length;
		if (n == 2) return Math.min(a[0], a[1]);
		for (int x : a) res = Math.min(res, x);
		return res;
	}
	
	static void cYes(boolean f) {
		System.out.println(f ? "Yes" : "No");
	}
	
	static void cYES(boolean f) {
		System.out.println(f ? "YES" : "NO");
	}
	
	static class Read {
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stringTokenizer = new StringTokenizer("");
		
		String next() {
			while (!stringTokenizer.hasMoreTokens()) {
				try {
					stringTokenizer = new StringTokenizer(bufferedReader.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return stringTokenizer.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
	
	static Read in = new Read();
	
	static int qpow(int a, int b) {
		int res = 1;
		a %= 9901;
		for (; b > 0; a = a * a % 9901, b >>= 1) if ((b & 1) == 1) res = res * a % 9901;
		return res;
	}
	
	static int sum(int a, int b) {
		if (b == 1) return 1;
		if (b % 2 == 0) return (1 + qpow(a, b / 2)) * sum(a, b / 2) % 9901;
		return (sum(a, b - 1) + qpow(a, b - 1)) % 9901;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a = in.nextInt(), b = in.nextInt();
		int res = 1;
		for (int i = 2; i * i <= a; i++) {
			//如果是，从2开始能保证是质数
			if (a % i == 0) {
				int cnt = 0; // 记录这个指数的次方
				while (a % i == 0) {
					a /= i;
					cnt++;
				}
				res = res * sum(i, b * cnt + 1) % 9901;
			}
		}
		if (a > 1) res = res * sum(a, b + 1) % 9901;
		if (a == 0) res = 0;
		System.out.println(res);
	}

}