【POJ 1845】 Sumdiv

【题目链接】

           点击打开链接

【算法】

         不妨先将A分解质因数

         A = p1^q1p2^p2p3^p3..pn^qn

         那么,A^B = p1^q1Bp2^q2B...pn^qnB

         根据约数和定理，A^B的约数和就是 ：

        (p1^0 + p1^1 + .. p1^q1B)(p2^0 + p2^1 + ... p2^q2B) ... (pn^0 + pn^1 + ... + pn^qnB)

        显然可以用等比数列求和来做，注意特判逆元不存在的情况

【代码】

         

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define P 9901

long long i,len,ans,A,B;

struct info
{
        long long p,q;
} d[100010];

inline long long power(long long a,long long n)
{
        long long ans = 1,b = a;
        while (n)
        {
                if (n & 1) ans = (ans * b) % P;
                b = (b * b) % P;
                n >>= 1;    
        }    
        return ans;
}
inline long long inv(long long x)
{
        return power(x,P-2);
}
inline long long calc(long long a,long long n)
{
        return (power(a,n+1) - a % P + P) % P * inv(a-1) % P;
}

int main() 
{
        
        scanf("%lld%lld",&A,&B);
        for (i = 2; i <= sqrt(A); i++)
        {
                if (A % i == 0)    
                {
                        d[++len] = (info){i,0};
                        while (A % i == 0)
                        {
                                A /= i;
                                d[len].q++;
                        }
                }
        }
        if (A > 1) d[++len] = (info){A,1};
        for (i = 1; i <= len; i++) d[i].q *= B;
        ans = 1;
        for (i = 1; i <= len; i++)
        {
                if ((d[i].p - 1) % P == 0) ans = (ans * (d[i].q + 1)) % P;
                else ans = (ans * (calc(d[i].p,d[i].q) + 1)) % P;
        }
        printf("%lld\n",ans);
                    
        return 0;
    
}
数学

相关

Liquidity Providers 的数学原理

『笔记』组合数学

组合数学练习

【YBTOJ高效进阶 21190】欧拉函数（数学）

北京市第14届大学生数学竞赛本科甲乙组试题及参考解答 北京市第14届大学生数学竞赛本

洛谷 P3711 - 仓鼠的数学题（多项式）

结对编程项目总结-带UI的小初高数学学习软件

大数据数学基础--用python实现微积分 20212311孙佳瑜

【数学】卢卡斯定理

数学软件

数学软件

[总结]多项式类数学相关（定理&证明&板子）

标签