POJ - 1845 Sumdiv 【约数个数定理 + 约数和定理 + 快速幂 + 逆元】

xiaoxiao2021-02-28  113

传送门 必备知识:

1 : 约数个数定理: 任意正整数都有且只有一种方式写出其素因子的乘积表达式。 A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn) 其中pi均为素数 2 : 约数和公式: 对于已经分解的整数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) 3 : 同余模公式: (a+b)%m=(a%m+b%m)%m (a*b)%m=(a%m*b%m)%m

//思路:有了以上知识, 那就比较简单了, 首先对A进行质因子分解, 那么A^B次方的因子和就是 res = (1+p1+p1^2+p1^3+…p1^k1*B) * (1+p2+p2^2+p2^3+….p2^k2*B) * (1+p3+ p3^3+…+ p3^k3*B) * …. * (1+pn+pn^2+pn^3+…pn^kn*B) 所以现在的关键就是求一个等比数列, 当然也比较简单, 就是一个求和公式, 但需要注意在求这个等比数列的和时, 我们可以看到涉及除法mod, 所以需要逆元, 还有就是分子有个减1, 所以有可能减出来是0(因为mod了的),就会导致最后答案是0(然分析可知, 最后应该是序列的长度, 也就是(幂+1) 的长度), 所以这个时候就需要分类讨论下, 即当质因子 p % mod == 1 时, 答案直接加上(幂+1).

AC Code

/** @Cain*/ #define ll long long int const int mod = 9901; ll A,B; ll qpow(ll x,ll y) { ll res = 1; while(y){ if(y&1) res = res*x%mod; x = x*x%mod; y >>= 1; } return res; } ll getsum(ll n,ll m) //求等比数列的前n项和. { //要使用逆元. return (((qpow(n,m)-1)%mod*qpow(n-1,mod-2) %mod) + mod)%mod; } void solve() { scanf("%lld%lld",&A,&B); ll res = 1; for(int i=2;i*i<=A;i++){ int ans = 0; while(A%i==0){ ans++; A/=i; } if(i % mod == 1) res = (res*(ans*B+1))%mod; //如前面所说,不懂就写出来看看. else res = (res%mod * getsum(i,ans*B+1))%mod; //否则就普通的算就是了. } if(A != 1){ if(A % mod == 1) res = (res*(B+1))%mod; //和前面一样. else res = (res%mod * getsum(A,B+1))%mod; } printf("%lld\n",res); }
转载请注明原文地址: https://www.6miu.com/read-46486.html

最新回复(0)