【Ybtoj 第29章例2】约数之和【同余问题】

解题思路

代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define ll long long

using namespace std;

const int mod = 9901;
ll A, B, cnt, ans = 1ll, pri[20010], v[200000010], c[2010];

void prime(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0)
            pri[++cnt] = i;
        while (x % i == 0) {
            c[cnt]++;
            x /= i;
        }
    }
    if (x > 1) {
        pri[++cnt] = x;
        c[cnt] = 1;
    }
}

ll ksm(ll a, ll x) {
    ll ans = 1, base = a;
    while (x) {
        if (x & 1)
            ans = ans * base % mod;
        base = base * base % mod;
        x = x >> 1;
    }
    return ans;
}

int main() {
    scanf("%lld%lld", &A, &B);
    prime(A);
    for (int i = 1; i <= cnt; i++) {
        if ((pri[i] - 1) % mod == 0) {
            ans = ans * (B * c[i] + 1) % mod;
            continue;
        }
        int w = ksm(pri[i], B * c[i] + 1);
        w = (w + mod - 1) % mod;
        int v = pri[i] - 1;
        v = ksm(v, mod - 2);
        ans = ans % mod * w * v % mod;
    }
    printf("%lld", ans);
}

最后

以上就是优雅小懒虫为你收集整理的【Ybtoj 第29章例2】约数之和【同余问题】的全部内容，希望文章能够帮你解决【Ybtoj 第29章例2】约数之和【同余问题】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。