POJ 1845 数学问题

雨点打透心脏的1/2处 2022-08-23 00:30 107阅读 0赞

求A^B的所有约数（即因子）之和，并对其取模 9901再输出。 (0 <= A,B <= 50000000)

我们首先要用到这样一个定理，数字A的所有因数之和，

对于已经分解的整数A=(p1^k1)\*(p2^k2)\*(p3^k3)\*....\*(pn^kn)

有A的所有因子之和为：

S = (1+p1+p1^2+p1^3+...p1^k1) \* (1+p2+p2^2+p2^3+….p2^k2) \* (1+p3+ p3^3+…+ p3^k3) \* .... \* (1+pn+pn^2+pn^3+...pn^kn)

所以对于A^B ， 假设A=(p1^k1)\*(p2^k2)\*(p3^k3)\*....\*(pn^kn)，那么A^B =  A^B = p1^(k1\*B) \* p2^(k2\*B) \*...\* pn^(kn\*B);

所以

**A^B的所有约数之和为：**

sum = \[1+p1+p1^2+...+p1^(a1\*B)\] \* \[1+p2+p2^2+...+p2^(a2\*B)\] \*...\* \[1+pn+pn^2+...+pn^(an\*B)\].

每一行都是等比数列，等比求和然后mod9901就可以了，本来可以用逆元来求解的，但是这个题目好像好点问题所以使用的是首位相乘递归二分递归的解法。

#include<cstdio>
    using namespace std;
    typedef long long ll;
    const ll MOD=9901;
    ll A,B;
    
    ll pow(ll p,ll n) //快速求幂 
    {
    	if(n==0)
    	{
    		return 1;
    	}
    	if(n&1)
    	{
    		return ( pow(p,n-1) * p ) % MOD;
    	}
    	ll ret=pow(p,n/2);
    	return ( ret * ret ) % MOD;
    }
    
    ll sum(ll p,ll n)  //等比求和 
    {
    	if(n==0)
    	{
    		return 1;
    	}
    	if(n&1)
    	{
    		return ( (1+pow(p,n/2+1)) * sum(p,n/2) ) % MOD;
    	}
    	return ( (1+pow(p,n/2+1)) * sum(p,n/2-1) + pow(p,n/2) )% MOD;
    } 
    
    ll cal()
    {
    	ll ans=1;
    	ll i,b;
    	for(i=2;i*i<=A;i++)
    	{
    		b=0;
    		while(A%i==0)
    		{
    			A/=i;
    			b++;
    		}
    		ans=(ans*sum(i,b*B))%MOD;
    	}
    	
    	if(A!=1)
    	{
    		ans=(ans*sum(A,B))%MOD;
    	}
    	return ans;
    }
    			
    int main()
    {
    	while(~scanf("%lld%lld",&A,&B))
    	{
    		printf("%lld\n",cal());
    	}
    	return 0;
    }