(poj1845)约数之和

港控/mmm° 2022-01-22 06:15 133阅读 0赞

题目链接： [https://www.acwing.com/problem/content/99/][https_www.acwing.com_problem_content_99]

本题应该说是一个数学问题了。首先暴力肯定是不行的。  
首先我们把A分解质因数，表示为p1^c1 \* p2 ^c2 \* ~~ pn ^ cn.。那么A^B就可以表示为  
p1^(c1 \* B) \* p2 ^(c2 \*B) ~~ pn ^ (cn \* B).  
那么很明显了，所有约数的集合就是p1^k1,p2 ^ k2 ~~ pn ^ kn.其中0<= ki <= B \* ci(1 <= i <= n)。  
到了这里我们在用分治的方法求出来就可以了。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    #define mod 9901
    typedef long long ll;
    
    ll A,B;
    
    ll kms(ll a,ll b)
    {
        ll ans = 1;
        a = a % mod;
        while(b)
        {
            if(b & 1)
            {
                ans = ans % mod * a % mod;
            }
            a = a % mod * a % mod;
            b = b >> 1;
        }
        return ans;
    }
    
    ll k_sum(ll p,ll limit)
    {
        if(limit == 0)
            return 1;
        if(limit & 1)//奇数的计算方法
            return (1 + kms(p,(limit + 1)/ 2)) * k_sum(p,(limit - 1) / 2) % mod;
        else//偶数的计算方法
            return ((1 + kms(p,limit >> 1)) * k_sum(p,limit / 2 - 1) + kms(p,limit)) % mod;
    }
    
    int main()
    {
        scanf("%lld%lld",&A,&B);
        if(A == 0)
            printf("0\n");
        else
        {
            ll sum = 1;
            for(ll i = 2; i <= A; i ++)
            {
                ll cnt = 0;
                while(A % i ==0 && A != 0)
                {
                    cnt ++; A = A / i;
                }
              //  printf("i = %d cnt = %d\n",i,cnt);
                sum *= k_sum(i,cnt * B);
                sum %= mod;
            }
            printf("%lld\n",(sum + mod) % mod);
        }
        return 0;
    }

[https_www.acwing.com_problem_content_99]: https://www.acwing.com/problem/content/99/