因子和

题目描述

输入两个正整数a和b，求\(a^b\)的因子和。结果太大，只要输出它对9901的余数。

解法

基本算数定理，每一个数都可以被分解成一系列的素数的乘积，然后你可以分解出因数了。

如何求出因数和呢？我们发现是等比数列，之后我们上等比数列求和公式就好了

\[S_n = \frac{a_1 \times (1-q^n)}{1-q}=\frac{p_{i}^{c_i+1} -1}{p_i -1}
\]

其中我们可以用快速幂和逆元求出来了

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstring>

#include <cstdio>

#include <cmath>

#define LL long long

using namespace std;

const LL mod = 9901;

LL ksm(LL x,LL y) {

	LL z=1;

	while(y) {

		if(y&1) z=(z*x)%mod;

		y>>=1;

		x=(x*x)%mod;

	}

	return z%mod;

}

LL to[2],get=1;

int main() {

	LL a=0,b=0,tmp,lim;

	scanf("%lld%lld",&a,&b);

	lim=sqrt(a);

	for(LL i = 2; i <= lim; i ++) {

		if(!(a%i)) {

			tmp=0;

			while(!(a%i)) {

				a/=i;

				tmp++;

			}

			to[1]=(tmp*b+1);

			if(i%mod==1) get=get*(tmp+1)%mod;

			else {

				to[0]=i%mod;

				get=get*(ksm(to[0],to[1])-1)*ksm(to[0]-1,mod-2)%mod;

			}

		}

	}

	if(a!=1) {

		to[1]=(b+1);

		if(a%mod==1)get=get*(b+1)%mod;

		else {

			to[0]=a%mod;

			LL k=(ksm(to[0],to[1])-1)*ksm(to[0]-1,mod-2)%mod;

			get=get*k%mod;

		}

	}

	printf("%lld",get);

	return 0;

}

巴特西

luogu 1593 因子和

因子和

题目描述

解法

最新文章

热门文章