约数之和

约数之和

题目描述

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

请你求出S mod 9901的值是多少。

输入格式

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

输出格式

输出一个整数,代表S mod 9901的值。

数据范围

$0≤A,B≤5×10^7$

输入样例:

2 3

输出样例:

15

注意: A和B不会同时为0。

题解

考虑将$A$进行质因数分解.

$A = \prod_{i = 1} ^ {n} p_i ^ {a_i} = p_1 ^ {a_1} p_2 ^ {a_2} p_3 ^ {a_3} p_n ^ {a_n}$

那么

$A^B = \prod_{i = 1} ^ {n} p_i ^ {a_i B} = p_1 ^ {a_1 B} p_2 ^ {a_2 B} p_3 ^ {a_3 B} p_n ^ {a_n * B}$

$S$定义为$A^B$的约数和,那么

$S = \prod_{i = 1}^n \sum_{j=0}^{a_i*B} p_i^j $

$S= (p_1^0+p_1^1+…+p_1^{a_1B})(p_2^0+p_2^1+…+p_2^{a_2B})(p_n^0+p_n^1+…+p_n^{a_nB})$

式子看似复杂,简单的讲就是相当于在式子中的每一个因子项。也就是每一个括号里面取一个。然后取得$n$相乘起来就得到了一个$A^B$的约数。

现在我们的问题就是求:$\sum_{j=0}^{a_i*B}p_i^j$

容易看出。这是一个等比数列前n项和。省赛就做过一个这个玩意儿。当时想复杂了。想成用等比数列前$n$项和公式,但是当时它那个题目的模数是输入,也就是模数可能是合数。这题中模数确定是9901。是一个素数。可以考虑使用等比数列求和公式。当然,可以使用分治,

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x"=" << x << endl;
typedef long long LL;
#define p first
#define a second
const int MOD = 9901;

LL powN(LL a, LL n){
    LL res = 1LL;
    while(n){
        if(n&1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

// 计算p^0+p^1+...+p^a
LL cal(LL p, LL a){
    if(a == 0) {
        return 1;
    }
    int h = a >> 1;
    if(!(a&1)){
        --h;
    }
    LL ans = cal(p, h);
    LL ah = powN(p, h+1);
    ans = (ans + ah * ans % MOD) % MOD;
    if(!(a&1)){
        ans = (ans + powN(p, a)) % MOD;
    }
    return ans;
}

int main(){
    //freopen("in.txt", "r", stdin);
    LL A,B;
    cin >> A >> B;
    if(A == 0 || A == 1){
        cout << A << endl;
        return 0;
    }
    map<LL, LL> mp;
    for(LL i = 2; i*i <= A; ++i){
        while(A%i == 0){
            mp[i]++;
            A /= i;
        }
    }
    if(A > 1) mp[A]++;
    LL ans = 1LL;
    for(auto x : mp){
        x.a *= B;
        ans = ans * cal(x.p, x.a) % MOD;
    }
    cout << ans << endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Round 524(Div. 2)

    需要邀请n个人来参加派对.需要制作邀请卡.一张邀请卡需要2红, 5绿, 8蓝. 每个笔记本有k个某种颜色.求最少需要多少个笔记本.

    xiaohejun
  • Wannafly挑战赛26

    题目大意: 平面坐标中有$$n$$个点.是否可以选择一个点作为圆心.其他$$n-1$$个点在这个圆上.

    xiaohejun
  • Educational_Codeforces_Round_81(Rated_for_Div. 2)_D题

    求$gcd(a, m) = gcd(a+x, m), 0 <= x < m, 1 <= a < m <= 10^{10}$的$x$的个数

    xiaohejun
  • Discrete Logging

    Description Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an int...

    attack
  • 数学--数论--组合数(卢卡斯+扩展卢卡斯)模板

    风骨散人Chiam
  • agc015F - Kenus the Ancient Greek(结论题)

    $Q$组询问,每次给出$[x, y]$,定义$f(x, y)$为计算$(x, y)$的最大公约数需要的步数,设$i \leqslant x, j \leqsla...

    attack
  • BZOJ3667: Rabin-Miller算法

    Description Input 第一行:CAS,代表数据组数(不大于350),以下CAS行,每行一个数字,保证在64位长整形范围内,并且没有负数。你需要对...

    attack
  • 51nod1004 n^n的末位数字

    题目来源: Author Ignatius.L (Hdu 1061) 基准时间限制:1 秒 空间限制:131072 KB 分值: 5  难度:1级算法题 给出一...

    attack
  • Day6下午题解1

    预计分数:100+?+30=130+? 实际分数:100+25+30=155 T1 https://www.luogu.org/problem/show?pid...

    attack
  • HGE系列之七 管中窥豹(图形界面)

    这次的HGE源码之旅,让我们来看看HGE的图形用户界面(GUI)的实现,话说电脑技术发展至今,当年轰动一时的图形用户界面,而今早已司空见惯,想来不得不感叹一下...

    用户2615200

扫码关注云+社区

领取腾讯云代金券