模板

判断质数

用试除法判断质数，有以下几种方式：

  1. 2 ~ n，这种方法最慢，不推荐。
  2. i * i ~ n，这种方法会爆 int，不推荐。
  3. i ~ n / i，与上一种方法相同，但是不爆 int，推荐。
  4. i ~ sqrt(n)，实测下来这个会更快，但是需要提前把 sqrt(n) 的结果存下来。
1
2
3
4
5
6
7
8
bool check(int n) {
    if (n < 2) return false;
    int s = sqrt(n);
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

时间复杂度：除了第一个都是 O(n)O(\sqrt{n})，还是比较可观的。

分解质因数

这里要用到一个结论，即对任意整数 nn 中比 n\sqrt{n} 大的质因数最多只有一个，可以用反证法证明。

因此，可以这样分解：

1
2
3
4
5
6
7
8
9
10
11
12
void factorize(int n) {
    for (int i = 2; i <= n / i; i++) {
        int cnt = 0;
        while (n % i == 0) {
            n /= i;
            cnt++;
        }
        if (cnt) cout << i << ' ' << cnt << '\n';
    }
    
    if (n != 1) cout << n << " 1\n";
}

实测这里用 2 ~ n/i 的方式更快，所以以后这种情况还是不用 sqrt 了。

埃式筛法

只以质数的倍数筛选，剩下的也全都是质数，这个容易证明。

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
#include <iostream>
#include <bitset>
using namespace std;

const int N = 1e6+10;
int cnt = 0, primes[N];
bitset<N> st;

void getprimes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            st[i] = 1;
            // 2*i, 3*i, 4*i, ...
            for (int j = 2*i; j <= n; j+=i) st[j] = 1;
        }
    }
}

int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int n;
    cin >> n;
    getprimes();
    cout << cnt << '\n';
    return 0;
}

线性筛法

每个合数只会被它的最小质因数筛掉：

1
2
3
4
5
6
7
8
9
10
void getprimes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        // 这里从小开始枚举质数 不断筛掉 primes[j]*i <= n
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = 1;
            if (i % primes[j] == 0) break;
        }
    }
}

着重关心一下内层 for 循环的原理，注意这里不管 ii 是质数还是合数都要筛选，不要把这层放到 if 里面去了：

  1. 如果 i mod pj=0i \text{ mod } p_j=0，由于 pjp_j 是从小开始找的，那么 pjp_j 一定是 ii 的最小质因数，可以证明 pjp_j 一定是 i⋅pji\cdot p_j 的最小质因数：

    • ii 的最小质因数是 pjp_j
    • 而 pjp_j 是质数
    • 所以 i⋅pji\cdot p_j 的最小质因数就是 pjp_j

  2. 如果 i mod pj≠0i \text{ mod } p_j \ne 0，由于 pjp_j 是从小开始找的，那么 pjp_j 一定比 ii 的最小质因数还小，那么 pjp_j 也一定是 i⋅pji\cdot p_j 的最小质因数：

    • ii 的最小质因数比 pjp_j 大
    • 而 pjp_j 是质数
    • 所以 i⋅pji\cdot p_j 的最小质因数还是 pjp_j

  3. 对于一个合数 xx 的最小质因子为 pp，归纳假设 pp 能被筛出来那么当 i=x/pi=x/p 时它就会被筛掉。

  4. 如果 ii 是质数，它会在 i=pji=p_j 时退出；如果 ii 是合数，它会在 pjp_j 筛到 ii 的最小质因子时退出。

约数个数

给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 10^9+7 取模。

  1. 对于任意一个数 nn，可以分解为以下形式，其中 pip_i 为一个质因数：

    n=p1α1⋅p2α2⋯pkαkn=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_k^{\alpha_k}

    那么，对于它的任何一个约数 mm 一定可以写成下面的形式：

    m=p1β1⋅p2β2⋯pkβkm=p_1^{\beta_1}\cdot p_2^{\beta_2}\cdots p_k^{\beta_k}

    每一个 βi\beta_i 都有 αi+1\alpha_i+1 种组合，根据乘法原理可以知道总个数是：

    N=(α1+1)(α2+1)⋯(αk+1)N=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)

  2. 除此之外，我们还要用到一个公式，即加法取模分配律：

    (a+b) mod c=(a mod c+b mod c) mod c(a+b)\text{ mod }c=(a\text{ mod }c+b\text{ mod }c)\text{ mod }c

    证明方式如下：

    a mod c=p,b mod c=qa=kc+p,b=mc+q⇒a+b=(k+m)c+p+qLHS=(p+q) mod c=RHS\begin{aligned} a\text{ mod }c&=p,b\text{ mod }c=q\\ a&=kc+p,b=mc+q\\ \Rightarrow a+b&=(k+m)c+p+q\\ \mathrm{LHS} &=(p+q)\text{ mod }c= \mathrm{RHS} \end{aligned}

所以只要知道公式本题难点不在这里，反而在于质因数分解容易写错。

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
#include <iostream>
#include <unordered_map>
using namespace std;

const int N = 1e9+7;

int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    unordered_map<int, int> primes;
    int n;
    cin >> n;
    while (n--) {
        int a;
        cin >> a;
        for (int i = 2; i <= a/i; i++) {
            while (a % i == 0) {
                a /= i;
                // operator[] 不存在时会新建
                primes[i]++;
            }
        }
        // 注意，a 还可能有一个比它开方大的因数 并且这一步是放到 for 循环下面的
        // 因为这是 a 在试完所有比 a 开方小的数之后留下的质因数
        if (a > 1) primes[a]++;
    }
    
    long long ans = 1;
    for (auto prime : primes) ans = (ans*(prime.second+1)) % N;
    cout << ans << '\n';
    return 0;
}

关于 primes[i]++ 这一步，可以找到 operator[] 的解释：

Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion if such key does not already exist.

From https://en.cppreference.com/w/cpp/container/unordered_map/operator_at

当访问不存在的元素时，它会自动插入，所以不必担心这点。

约数之和

给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 10^9+7 取模。

  1. 对于所有约数之和，如下：

    S=(p10+p11+⋯+p1α1)⋯(pk0+pk1+⋯+pkαk)S=∏i=0k∑j=1αipijS=(p_1^0+p_1^1+\cdots+p_1^{\alpha_1})\cdots(p_k^0+p_k^1+\cdots+p_k^{\alpha_k})\\ S=\prod_{i=0}^k \sum_{j=1}^{\alpha_i} p_i^{j}

    这个可以简要说明：对于这个多项式相乘的每一项都有 αi+1\alpha_i+1 种组合，合起来就是 NN 种组合，而且各不相同，因此这些多项式展开最终就会得到约数之和。

  2. 此外，这个题还要用到一个取模的公式，如下：

    (ab) mod c=((a mod c)(b mod c)) mod c(ab)\text{ mod }c=((a\text{ mod }c)(b\text{ mod }c))\text{ mod }c

    证明如下（用到了前面提到的加法取模分配律）：

    a mod c=p,b mod c=q⇒a=kc+p,b=mc+qab=kmc2+kqc+mpc+pq=(kmc+kq+mp)c+pq⇒LHS=(pq) mod c=RHS\begin{aligned} a\text{ mod }c&=p,b\text{ mod }c=q\\ \Rightarrow a&=kc+p,b=mc+q\\ ab&=kmc^2+kqc+mpc+pq\\ &=(kmc+kq+mp)c+pq\\ \Rightarrow \text{LHS}&=(pq)\text{ mod }c=\text{RHS} \end{aligned}

    可以看出，模的性质很多时候都可以把它用一个等式表示出来之后再进行推导。

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
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 1e9+7;

int main() {
    unordered_map<int, int> primes;
    int n;
    cin >> n;
    
    while (n--) {
        int a;
        cin >> a;
        for (int i = 2; i <= a/i; i++) {
            while (a % i == 0) {
                a /= i;
                primes[i]++;
            }
        }
        if (a > 1) primes[a]++;
    }
    
    long long ans = 1;
    for (auto prime : primes) {
        int p = prime.first, a = prime.second;
        long long t = 1;
        // t = p^0+p^1+...+p^a
        // 这一步在求哈希值的时候也用过 本质上相当于一个 p 进制数的每位都为1
        // 一共有 a+1 位, 这里如果循环一次那么这个数字是 p 进制的 11
        // 所以循环 a 次就够了
        while (a--) t = (t*p+1) % N;
        
        ans = (ans * t) % N;
    }
    
    cout << ans << '\n';
    return 0;
}

对于后面的两个 % N 操作，我们可以把模的乘法分配律和模的加法分配律自由组合，而且由加法结合律也可以把多项式中的几项任意组合然后取模，结果也是不会改变的，所以 t = (t*p+1)%N 最后求得的就是这个等比数列前a+1 项和模 N，(ans * t) % N 最后也能算到一个正确的结果。

最大公约数

辗转相除法：

gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a, b)=\gcd(b,a\text{ mod }b)

这个证明起来也是比较容易的，设 d 是 a 和 b 的任意一个公约数，都有如下式子：

a mod b=a−⌊ab⌋b=a−kba=md,b=nd⇒a−kb=md−knd=(m−kn)d\begin{aligned} a\text{ mod }b&=a-\lfloor\frac{a}{b}\rfloor b=a-kb\\ a&=md, b=nd\\ \Rightarrow a-kb&=md-knd=(m-kn)d \end{aligned}

所以 a 和 b 与 b 和 a%b 的所有约数都相等，那么最大公约数自然也相等。

1
2
3
int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

下面是例题。

例题

质数距离

给定两个整数 L 和 U，你需要在闭区间 [L,U] 内找到距离最接近的两个相邻质数 C1 和 C2（即 C2−C1 是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数 D1 和 D2 即 D1−D2 是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。

输入格式

每行输入两个整数 L 和 U，其中 L 和 U 的差值不会超过 1e6。

输出格式

对于每个 L 和 U，输出一个结果，结果占一行。

结果包括距离最近的相邻质数对和距离最远的相邻质数对。（具体格式参照样例）

如果 L 和 U 之间不存在质数对，则输出 There are no adjacent primes.。

数据范围

1≤L<U≤231−11\le L \lt U \le 2^{31}-1

题目链接：AcWing 196。

如何筛出 [L,U][L, U] 的所有质数是本题主要难点，这里的做法是，如果一个数 xx 是合数，那么它一定存在一个质因子 p≤xp\le \sqrt x，因此找出数据范围内的所有小于等于 N\sqrt N 的质数然后排除掉它们的倍数就可以。

大于 LL 的第一个 PP 的倍数是 ⌈LP⌉P=⌊L+P−1P⌋P\lceil \cfrac{L}{P}\rceil P=\lfloor \cfrac{L+P-1}{P} \rfloor P

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
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 1e6+10;
// 1~sqrt 2^31-1<50000
vector<int> primes, plr;
bool st[N];

void init() {
    const int n = 50000;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes.emplace_back(i);
        for (int j = 0; primes[j] <= n/i; j++) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    init();
    int l, r;
    while (~scanf("%d%d", &l, &r)) {
        memset(st, 0, sizeof st);
        plr.clear();
        for (LL p : primes) {
            for (LL j = max(2 * p, (l+p-1)/p*p); j <= r; j += p) {
                st[j-l] = true;
            }
        }
        for (int i = 0; i <= r-l; i++)
            // 质数不能是 1
            if (!st[i] && i+l >= 2)
                plr.emplace_back(i+l);
        
        if (plr.size() < 2) {
            puts("There are no adjacent primes.");
            continue;
        }
        
        // Find
        int maxp = 0, minp = 0;
        for (int i = 0; i < plr.size() - 1; i++) {
            int d = plr[i+1] - plr[i];
            if (d > plr[maxp+1] - plr[maxp]) maxp = i;
            if (d < plr[minp+1] - plr[minp]) minp = i;
        }
        printf(
            "%d,%d are closest, %d,%d are most distant.\n",
            plr[minp], plr[minp+1], plr[maxp], plr[maxp+1]
        );
    }
    return 0;
}

阶乘分解

给定整数 N，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。

原题链接：AcWing 197。

一个朴素的想法是直接从 2, 3, ..., N 全部分解质因数，这样的复杂度是 O(nn)O(n\sqrt n)，会超时那也比先求出来阶乘再分解效率高：

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
#include <iostream>
using namespace std;

const int N = 1000010;

int ans[N], n;

void factorize(int t) {
    for (int i = 2; i <= t/i && t != 1; i++) {
        while (t % i == 0) {
            ans[i]++;
            t /= i;
        }
    }
    
    if (t != 1) ans[t]++;
}

int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) factorize(i);
    for (int i = 2; i <= n/i; i++) {
        if (ans[i]) printf("%d %d\n", i, ans[i]);
    }
    
    return 0;
}

先筛出数据范围 1∼1061\sim 10^6 所有质数，然后对于每个质数 pp，从 1∼n1\sim n 中是 pp 的倍数的数字的个数是 ⌊np⌋\lfloor \cfrac{n}{p} \rfloor，不断累加 p2,p3,⋯ ,pkp^2,p^3,\cdots,p^k 就可得到质因子的数量，因为 pkp^k 需要被累加 kk 次。

cnt(p)=∑i=1pi≤n⌊npi⌋\text{cnt}(p)=\sum_{i=1}^{p^i\le n} \lfloor \frac{n}{p^i} \rfloor

在 NN 个数中筛出所有质数，然后对每个质数进行对数级别的操作，结合素数分布定理，在 NN 个数中质数有 Nln⁡N\cfrac{N}{\ln N} 个，那么最终的复杂度就是 O(N+Nln⁡Nlog⁡N)=O(N)O(N+\cfrac{N}{\ln N} \log N)=O(N)

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
#include <cstdio>
#include <vector>
using namespace std;

typedef long long LL;
const int N = 1e6+10;
bool st[N];
vector<int> primes;

void getprimes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes.emplace_back(i);
        for (int j = 0; primes[j] <= n/i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    getprimes(n);
    for (int p: primes) {
        int cnt = 0;
        for (LL j = p; j <= n; j *= p) cnt += n/j;
        printf("%d %d\n", p, cnt);
    }
    return 0;
}

二元方程整数解

给定整数 n∈[1,106]n\in [1, 10^6]，求多少对正整数 (x,y)(x, y) 满足方程 1x+1y=1n!\cfrac{1}{x}+\cfrac{1}{y}=\cfrac{1}{n!}

题目链接：AcWing 1294。

化简一下。

1y=1n!−1x=x−n!xn!y=xn!x−n!=(x−n!+n!)n!x−n!=n!+(n!)2x−n!\begin{aligned} \frac{1}{y}&=\frac{1}{n!}-\frac{1}{x}\\ &=\frac{x-n!}{xn!}\\ y&=\frac{xn!}{x-n!}\\ &=\frac{(x-n!+n!)n!}{x-n!}\\ &=n!+\frac{(n!)^2}{x-n!} \end{aligned}

也就转化成了 (n!)2(n!)^2 的约数个数，若 n!=∏picin!=\prod p_i^{c_i}，则 (n!)2=∏pi2ci(n!)^2=\prod p_i^{2c_i}，约数个数就是 ∏(2ci+1)\prod(2c_i+1)

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
#include <cstdio>
#include <vector>
using namespace std;

typedef long long LL;
const int N = 1e6+10, mod = 1e9+7;
vector<int> primes;
bool st[N];

void init() {
    const int n = 1e6;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes.emplace_back(i);
        for (int j = 0; primes[j] <= n/i; j++) {
            st[primes[j]*i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    init();
    
    int n; scanf("%d", &n);
    LL ans = 1;
    for (int p : primes) {
        int cnt = 0;
        for (LL j = p; j <= n; j *= p) {
            cnt += n / j;
        }
        ans = (ans * (2 * cnt + 1) % mod) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}

反素数

对于任何正整数 x，其约数的个数记作 g(x)，例如 g(1)=1、g(6)=4。

如果某个正整数 x 满足：对于任意的小于 x 的正整数 i，都有 g(x)>g(i)，则称 x 为反素数。

例如，整数 1，2，4，6 等都是反素数。

现在给定一个数 N，请求出不超过 N 的最大的反素数。

题目链接：AcWing 198。

首先，反素数就是 1∼N1\sim N 中约数个数最多的数字，然后如果有多个数字约数个数相同，取最小的那个。

本题还有性质：不同的质因子数量不会太多，最多只有 9 个，这个可以从小开始枚举素数算一下。如果一个数是反素数，那么它的次数是按照质因子的大小非严格降序排列，比如 36×573^6\times 5^7 和 37×563^7\times 5 ^ 6 的约数个数相同，但 显然前者是更优的

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
#include <iostream>
using namespace std;

typedef long long LL;
int primes[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
int n, maxd, number;

// 素数索引 上一个次数 乘积 约数个数
void dfs(int u, int last, int p, int d) {
    if (d > maxd || d == maxd && p < number) {
        maxd = d;
        number = p;
    }
    
    if (u == 9) return;
    
    for (int i = 1; i <= last; i++) {
        if ((LL)p * primes[u] > n) break;
        p *= primes[u];
        dfs(u+1, i, p, d*(i+1));
    }
}

int main() {
    cin >> n;
    dfs(0, 30, 1, 1);
    cout << number << endl;
    return 0;
}

Hackson 的趣味题

已知正整数 a0,a1,b0,b1a_0,a_1,b_0,b_1，设某未知正整数 x 满足：

  1. x 和 a0 的最大公约数是 a1；
  2. x 和 b0 的最小公倍数是 b1。

求解满足条件的 x 的个数。

原题链接：AcWing 200，P1072。

求解满足方程 gcd⁡(x,a0)=a1,lcm(x,b0)=b1\gcd(x,a_0)=a_1, \text{lcm}(x, b_0)=b_1 的解的个数，那么 xx 必然是 b1b_1 的约数，枚举所有 b1b_1 的约数然后检测是否满足 gcd⁡(x,a0)=a1\gcd(x,a_0)=a_1 就可以了。

如果用试除法枚举 b1b_1 约数，那么至少需要 b1\sqrt {b_1} 的复杂度，这样总复杂度是：

nb=2000×2×109=45×107n\sqrt b=2000\times \sqrt {2\times 10^9}=4\sqrt {5} \times 10^7

会被卡掉，因此我们先筛出所有小于 b\sqrt 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
#include <cstdio>
#include <vector>
using namespace std;

// sqrt b
const int N = 45000;

struct Factor { int p, s; };
vector<Factor> factors;
vector<int> primes;

bool st[N+1];
int a0, a1, b0, b1, ans;

void init() {
    for (int i = 2; i <= N; i++) {
        if (!st[i]) primes.push_back(i);
        for (int j = 0; primes[j] <= N/i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break; 
        }
    }
}

void factorize(int t) {
    factors.clear();
    
    for (int p : primes) {
        if (t == 1) break;
        int s = 0;
        while (t % p == 0) s++, t /= p;
        if (s) factors.push_back({p, s});
    }
    
    if (t != 1) factors.push_back({t, 1});
}

int gcd(int a, int b) { return a ? gcd(b%a, a) : b; }
int lcm(int a, int b) { return (long long)a*b / gcd(a, b); }

void dfs(int u, int p) {
    if (u >= factors.size()) {
        if (gcd(p, a0) == a1 && lcm(p, b0) == b1) ans++;
        return;
    }
    
    for (int s = 0; s <= factors[u].s; s++) {
        dfs(u+1, p);
        p *= factors[u].p;
    }
}

int solve() {
    scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
    if (b1 % b0 != 0) return 0;
    
    factorize(b1);
    ans = 0;
    dfs(0, 1);
    return ans;
}

int main() {
    init();
    int T; scanf("%d", &T);
    while (T--)
        printf("%d\n", solve());
    return 0;
}

约数之和

已知自然数 A,BA, B 且 SS 是 ABA^B 的所有约数之和。

求 S mod 9901S \text{ mod } 9901 的值。

题目链接：AcWing 97。

先分解 AA，然后对于约数之和的每一项都看作等比数列，求等比数列 p0∼pαBp^0\sim p^{\alpha B} 的和，也就是：

pαB+1−1p−1≡(pαB+1−1)(p−1)−1(mod 9901)\frac{p^{\alpha B+1}-1}{p-1} \equiv (p^{\alpha B+1}-1)(p-1)^{-1} (\text{mod }9901)

当 p−1≡0,p≡1p-1 \equiv 0,p\equiv 1 时，pi≡1p^i \equiv 1，此时求和结果就是 (αB+1) mod 9901(\alpha B+1) \text{ mod } 9901

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
#include <cstdio>
#include <unordered_map>
using namespace std;

typedef long long LL;
const int mod = 9901;
unordered_map<int, int> f;
int A, B;

void factorize() {
    for (int i = 2; i <= A/i; i++) {
        while (A % i == 0) {
            f[i]++;
            A /= i;
        }
    }
    if (A > 1) f[A] = 1;
}

LL qmi(LL a, LL k) {
    LL res = 1;
    while (k) {
        if (k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

int main() {
    scanf("%d%d", &A, &B);
    if (A == 0) {
        puts("0");
        return 0;
    }
    
    factorize();
    LL res = 1;
    for (const auto& fa : f) {
        LL k = fa.second * B, p = fa.first;
        if (p % mod == 1) {
            res = res * (k + 1) % mod;
        } else {
            res = res * ((qmi(p, k+1) - 1) * qmi(p - 1, mod-2)) % mod;
        }
    }
    printf("%lld\n", (res + mod) % mod);
    return 0;
}