POJ1845

这还是一道综合了许多数论的知识点的，做完也涨了不少姿势

但还是因为约数和公式这个鬼东西去找了度娘

题意很简单，就是求\(A^B\)的约数之和\(mod\ 9901\)。

但是这种题意越是简单的题目越是坑人

首先如果你不知道约数和公式就绝逼GG，然后由于有唯一分解定理这种东西撑腰，我们选择直接用公式.

先分解质因数得到\(n\)个质因数\(p_i\)和它们出现的次数\(t_i\)，然后约数和：

\(\prod_{i=1}^{n} \sum_{j=0}^{t[i]} {p_i}^j\)

然后我们考虑如何处理那个\(\sum_{j=0}^{t} {p}^j\)

首先我们可以发现这是一个等比数列，然后我们来对它进行转化，我们设\(S=\sum_{j=0}^{t} {p}^j ......(1)\)，则有

\(pS=\sum_{j=1}^{t+1} {p}^j ......(2)\)

我们\((2)-(1)\)得

\((p-1)S=p^{t+1}-1\)

即

\(S=\frac{p^{t+1}-1}{p-1}\)

所以我们上面用快速幂，下面用逆元即可，然后就解决了

但其实这道题的坑点让人难以想象：

当\(9901\mid p-1\)时不能用逆元，要特殊处理
因为这道题的次数不能取模，所以要涉及到两个long long的数相乘，但是由于取模所以不用高精，所以我们用二进制的方法（其实就是和快速幂一样的思想）来做快速乘
分解质因数的时候这个数可能本身就是质数（这个比较经典）

然后我们就可以艹过去了

CODE

#include<cstdio>

using namespace std;

typedef long long LL;

const LL S_N=10005,mod=9901;

LL a,b,prime[S_N],t[S_N],ex,cnt,ans=1;

bool vis[S_N];

inline void Euler(LL m)

{

	register LL i,j; vis[1]=1;

	for (i=2;i<m;++i)

	{

		if (!vis[i]) prime[++cnt]=i;

		for (j=1;j<=cnt&&i*prime[j]<m;++j)

		{

			vis[i*prime[j]]=1;

			if (!(i%prime[j])) break;

		}

	}

}

inline void resolve(LL x)

{

	register LL i;

	for (i=1;i<=cnt;++i)

	{

		while (!(x%prime[i])) x/=prime[i],++t[i];

		if (!(x^1)) break;

	}

	if (x^1) ex=x;

}

inline LL quick_mul(LL x,LL y,LL mod)

{

	LL tot=0;

	while (y)

	{

		if (y&1) tot=(tot+x)%mod;

		x=(x<<1)%mod; y>>=1;

	}

	return tot;

}

inline LL quick_pow(LL x,LL p,LL mod)

{

	LL tot=1;

	while (p)

	{

		if (p&1) tot=quick_mul(tot,x,mod);

		x=quick_mul(x,x,mod); p>>=1;

	}

	return tot;

}

inline LL inv(LL x)

{

	return quick_pow(x,mod-2,mod);

}

inline LL calc(LL p,LL t)

{

	return (((quick_pow(p,t,mod)-1+mod)%mod)*inv(p-1))%mod;

}

int main()

{

	Euler(S_N); scanf("%lld%lld",&a,&b); resolve(a);

	for (register LL i=1;i<=cnt;++i)

	if (t[i])

	{

		if ((prime[i]-1)%mod) ans=(ans*calc(prime[i],t[i]*b+1))%mod;

		else ans=(ans*quick_pow(prime[i],t[i]*b+1,mod*(prime[i]-1))/(prime[i]-1))%mod;

	}

	if (ex)

	{

		if ((ex-1)%mod) ans=(ans*calc(ex,b+1))%mod;

		else ans=(ans*quick_pow(ex,b+1,mod*(ex-1))/(ex-1))%mod;

	}

	printf("%lld",ans);

	return 0;

}

巴特西

POJ1845

最新文章

热门文章