程序员经验分享-hwhale

【Luogu】P1593因子和（唯一分解定理，约数和公式）

2023-05-16

题目链接

首先介绍两个定理。

整数唯一分解定理：任意正整数都有且只有一种方式写出素数因子的乘积表达式。

\(A=(p1k1 p2k2 ...... pnkn \)

求这些因子的代码如下


for(int i=2;i*i<=a;++i){
        if(!(a%i)){
            prime[++num]=i;
            while(!(a%i)){
                a/=i;
                sum[num]++;
            }
        }
    }
    if(a!=1){
        prime[++num]=a;
        sum[num]=1;
    }
唯一分解定理

约数和公式：对于已经分解的整数A，有A的所有因子和为

\( S= (1+p1+p12+p13+......+p1k1) (1+p2+p22+p23+......+p2k2)........(1+pn+pn2+pn3+......+pnkn) \)

所以局势明朗。用快速幂求出p的k*b次方，然后递归求和。代码如下


long long Sum(long long p,long long n){
    if(n==0)    return 1;
    if(n&1)    return (Sum(p,n>>1)*(1+Pow(p,(n>>1)+1)))%mod;
    return     (Sum(p,(n>>1)-1)*(1+Pow(p,(n>>1)+1))+Pow(p,n>>1))%mod;
}

解题代码如下


#include<cstdio>
#include<cctype>
#define mod 9901
inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}

int prime[10000];
int sum[10000];
int num;

long long Pow(long long n,long long i){
    if(i==0)    return 1;
    if(i==1)    return n%mod;
    long long ret=Pow(n,i>>1);
    if(i&1)    return (((ret*ret)%mod)*n)%mod;
    return (ret*ret)%mod;
}

long long Sum(long long p,long long n){
    if(n==0)    return 1;
    if(n&1)    return (Sum(p,n>>1)*(1+Pow(p,(n>>1)+1)))%mod;
    return     (Sum(p,(n>>1)-1)*(1+Pow(p,(n>>1)+1))+Pow(p,n>>1))%mod;
}

int main(){
    long long a=read(),b=read();
    for(int i=2;i*i<=a;++i){
        if(!(a%i)){
            prime[++num]=i;
            while(!(a%i)){
                a/=i;
                sum[num]++;
            }
        }
    }
    if(a!=1){
        prime[++num]=a;
        sum[num]=1;
    }
    int ans=1;
    for(int i=1;i<=num;++i)
        ans=(ans*Sum(prime[i],sum[i]*b)%mod)%mod;
    printf("%d",ans);
    return 0;
}

 

转载于:https://www.cnblogs.com/cellular-automaton/p/7483285.html

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

【Luogu】P1593因子和（唯一分解定理，约数和公式） 的相关文章

随机推荐

  • 数据结构|-常见数据结构整理

    归纳总结了一下数据机构的常用类型 xff0c 个人理解常用的数据机构可以分为线性表 栈 队列 树 xff0c 线性表包括顺序表和链表 xff0c 栈和队列应当属于特殊的线性表 xff0c 有几个概念和误区需要先说一下 顺序表和线性表的关系

  • Xcode5 创建模板和UIView 关联XIB

    来源 xff1a http www cnblogs com china ldw p 3533896 html 在做ios应用开发的过程 xff0c 难免遇到要创建 子view 和 自定义view的时候 xff0c 归根到底 xff0c 我们

  • opencv中矩阵计算的一些函数

    转自 xff1a http blog sina com cn s blog 7908e1290101i97z html 综述 OpenCV有针对矩阵操作的C语言函数 许多其他方法提供了更加方便的C 43 43 接口 xff0c 其效率与Op

  • mysql中对比 JSON_VALUE 与 JSON_QUERY

    1 JSON概述 MySQL里的json分为json array和json object 表示整个json对象 xff0c 在索引数据时用下标 对于json array xff0c 从0开始 或键值 对于json object xff0c

  • Win10系统的Microsoft Edge浏览器打开任一网页均未响应卡死的问题

    Edge浏览器在刚装上WIN10的时候就使用了 xff0c 的确给人耳目一新 xff0c 使用起来也非常顺心的感觉 xff0c 总体上还是很感人的 xff0c 可是今天使用突然出现随便打开一个网页都会卡死 xff0c 未响应的问题 xff0

  • 用二进制方法求两个整数的最大公约数(GCD)

    二进制GCD算法基本原理是 先用移位的方式对两个数除2 xff0c 直到两个数不同时为偶数 然后将剩下的偶数 xff08 如果有的话 xff09 做同样的操作 xff0c 这样做的原因是如果u和v中u为偶数 v为奇数 xff0c 则有gcd

  • SQL SERVER解析Json

    外包的项目 xff0c 有很多信息存储在JSON中 xff0c 无论是查询还是修改信息都十分麻烦 找了一些实用的SQL Function去解析 xff0c 并附修改例子 使用过程 xff1a 1 需要在SQL新建自定义类型 table Hi

  • c++ 头文件循环引用解法

    A h include 34 B h 34 class A public B m b B h include 34 A h 34 class B public A m a 上面这样是编译不过的 xff0c 把A h中的 include 34

  • 搭建ceph集群（单节点）

    https blog csdn net Greenchess article details 77525786 软件环境 xff1a Centos7 x64 CEPH版本 xff1a ceph deploy v1 5 37 ceph ver

  • Java-SpringCloud-基础

    一 服务注册与发现 服务注册 xff1a 服务提供者将服务的信息 xff08 IP 端口 协议等 xff09 登记到注册中心服务发现 xff1a 服务消费者根据一定策略从注册中心的服务列表选取一个服务 1 eureka span class

  • Ubuntu休眠不能唤醒问题之分区惹的祸

    问题描述 xff1a 休眠后进行唤醒时一直黑屏或内核错误 经历如下 xff1a 在笔记本上添加了固态硬盘后直接将机械硬盘上的系统拷贝到固态盘中使用 xff0c 设置了swap分区 xff0c 在唤醒时内核报告ext4文件系统错误 在lily

  • 用Keil-MDK开发TQ2440裸机程序入门教程——LED流水灯实现

    觉得此编文章很详实 xff0c 故转载之 xff0c 来自http www amobbs com thread 5281512 1 1 html 开发板也差不多买了半年了 以前照着教程用的是软件是ADS 在win7下老是崩溃 后来才知道AD

  • 【洛谷 3366】最小生成树_Prim

    题目描述 如题 xff0c 给出一个无向图 xff0c 求出最小生成树 xff0c 如果该图不连通 xff0c 则输出orz 输入格式 第一行包含两个整数N M xff0c 表示该图共有N个结点和M条无向边 xff08 N lt 61 50

  • 远程rdp vnc连接 UBuntu 10.10

    我打算用ubuntu编译Android源码 xff0c 因为编译时间较长需要远程控制一下自己的电脑 xff0c 所以想到了安装远程桌面软件 xff0c 具体方法 xff1a Ubuntu下的操作 1 Win7远程连接上Ubuntu xff0

  • AtCoder ABC 140E Second Sum

    题目链接 xff1a https atcoder jp contests abc140 tasks abc140 e 题目大意 给定一个 1 N 的排列 P 定义 X L R 的值为 P L P L 43 1 ldots P R 中第二大的

  • Sublime MinGw实现C/C++代码编译运行

    安装配置MinGw 下载安装MinGW 去官网下载MinGw xff1a http www mingw org 或者下载我已经下载好的完整版 xff1a http pan baidu com s 1gfgluin 2017 7 5更新 如图

  • Ajax发送POST请求SpringMVC页面跳转失败

    问题描述 xff1a 因为使用的是SpringMVC框架 xff0c 所以想使用ModelAndView进行页面跳转 思路是发送POST请求 xff0c 然后controller层中直接返回相应ModelAndView xff0c 但是这种

  • Debian命令

    1 dpkg i 安装下载的软件包 2 shutdown h now 关机 3 fdisk l 查看当前盘 4 lspci 用来显示系统中所有PCI总线设备或连接到该总线上的所有设备的工具 如lspci v 参数 xff1a v 使得 ls

  • 堡垒机-teleport的安装以及常见问题解决办法

    teleport是一款简单易用的堡垒机系统 xff0c 运用在企业对windows linux服务器的安全使用管理以及审计 官网网址 xff1a http teleport eomsoft net github地址 xff1a https

  • 【Luogu】P1593因子和（唯一分解定理，约数和公式）

    题目链接 首先介绍两个定理 整数唯一分解定理 xff1a 任意正整数都有且只有一种方式写出素数因子的乘积表达式 A 61 p1k1 p2k2 pnkn 求这些因子的代码如下 for int i 61 2 i i lt 61 a 43 43

热门标签