Sumdiv

title: Sumdiv
date: 2023-12-12 21:45:09
tags: 分治
categories: 算法进阶指南

题目大意

求 $A^B$ 的所有约数之和 $mod$ $9901$($1$ $\le$ $A,B$ $\le$ $5?10^7$)

解题思路

将 $A$ 分解质因数，表示为 $p{1}^{c_1}$ * $p{2}^{c_2}$ * …… * $p{n}^{c_n}$,那个 $A?B$ 就为 $p{1}^{B?c_1}$ * $p{2}^{B?c_2}$ * …… * $p{n}^{B?c_n}$
根据乘法分配律， $A^B$ 所有约数的和就是：
($1+p_1+\dots \dots +p_1^{B?c_1}$) * ($1+p_2+\dots \dots +p_n^{B?c_2}$) * …… * ($1+p_n+\dots \dots +p_n^{B?c_n}$)
比如：$360$ = $2^3?3^2?5^1$,约数之和为 $(2^0+2^1+2^2+2^3)?(3^0+3^1+3^2)?(5^0+5^1)$
约数个数为 $(3+1)?(2+1)?(1+1)$
每一个括号都是等比数列，使用分治法进行等比数列的求和。
问题转化为：
使用分治法求 sum(p,c) = $1+p+p^2+\dots \dots +p^c$ = ?
若 $c$ 为奇数：sum(p,c) = (1 + $p^{c+1}$) * sum(p,(c - 1) / 2);
若 $c$ 为偶数：sum(p,c) = (1 + $p^{c/2}$) * sum(p,c / 2 - 1) + $p^c$;
每一次分治之后，问题的规模会缩小一半，配合快速幂即可在 $O(logc)$ 的时间内求出等比数列的和。

代码实现

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

typedef long long LL;

const int N = 1314;

const int MOD = 9901;

LL kmi(LL a,LL k)
{
	LL ans = 1;
    a %= MOD;
	for(;k ; k >>= 1){
		if(k & 1){
			ans = ans * a % MOD; 
		}
		a = a * a % MOD;
	}
	return ans;
}

LL sum(LL p,LL c)
{
    if(c == 0) return 1; 
	else if(c & 1){
		return (1 + kmi(p,(c + 1) / 2) % MOD) * sum(p,(c - 1) / 2) % MOD;
	}
	else{
		return (1 + kmi(p,c / 2)) % MOD * sum(p,c / 2 - 1)  % MOD+ kmi(p,c) % MOD;
	}
}

unordered_map<LL,LL> cnt;
int main()
{
	LL A,B;
	cin >> A >> B;
	
	for(int i = 2; i <= A / 2 ; i ++){
		while(A % i == 0){
			A /= i;
			cnt[i] ++; 
		}
	}
	if(A == 0){
        cout << 0 << endl;
        return 0;
    }
	if(A > 1) cnt[A] ++;
	LL ans = 1;
	for(auto x : cnt){
       // cout << x.first << ' ' << x.second << endl;
		ans *= sum(x.first,x.second * B);
		ans %= MOD;
	}
	cout << ans  << endl;
}