热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

求等比数列前n项和(约数之和)

原题链接法一:分治法思路这里是实现一个sum函数,sum(p,k)表示\[p^0+p^1+p^{k-1}\]当k为偶数时,sum(p,k)可以拆解成\[p^0+p^1+

原题链接


法一:分治法


思路

这里是实现一个sum函数,sum(p,k)表示

\[p^0+p^1+...p^{k-1}
\]

当k为偶数时,sum(p,k)可以拆解成

\[p^0+p^1+...+p^{k/2-1}+p^{k/2}+...+p^{k-1}
\]

\[p^0+p^1+...+p^{k/2-1}+p^{k/2}*(p^0+p^1+...+p^{k/2-1})
\]

也就是

\[sum(p,k/2)+p^{k/2}*sum(p,k/2)
\]

进一步化简

\[(p^{k/2}+1)*sum(p,k/2)
\]

当k为奇数时,为了方便调用我们写的偶数项情况,可以单独把最后一项拿出来,剩下的化为求偶数项的情况来考虑,再加上最后一项,就是奇数项的情况了,即

\[sum(p,k-1)+p^{k-1}
\]

代码

#include
#include
using namespace std;
typedef long long LL;
const int mod = 9901;
int A, B;
//保存质因子以及出现的次数
unordered_map primes;
//试除法质因子分解
void divide(int n) {
for(int i = 2; i <= n / i; i++) {
if(n % i == 0) {
while(n % i == 0) {
primes[i]++;
n /= i;
}
}
}
if(n > 1) {
primes[n]++;
}
}
//快速幂
int qmid(int a, int b) {
int res = 1;
while(b) {
if(b & 1) res = (LL)res * a % mod;
a = (LL)a * a % mod;
b >>= 1;
}
return res;
}
//p0 + .. + pk-1
int sum(int p, int k) {
if(k == 1) return 1; //边界
if(k % 2 == 0) {
return (LL)(qmid(p, k / 2) + 1) * sum(p, k / 2) % mod;
}
return (qmid(p, k - 1) + sum(p, k - 1)) % mod;
}
int main(){
cin >> A >> B;
//对A分解质因子
divide(A);
int res = 1;
for(auto it : primes) {
//p是质因子,k是质因子的次数
int p = it.first, k = it.second * B;
// res要乘上每一项, 注意这里是k + 1
res = (LL)res * sum(p, k + 1) % mod;
}
if(!A) res = 0;
cout < return 0;
}

法二:公式法


思路

可以直接套用等比数列求和公式

\[\frac{a_1(p^n-1)}{p-1}
\]


  • 分母p-1是mod的倍数,则不存在逆元,这时直接乘(1+p+...p^k)%mod,即k+1

    这时因为如果p-1是mod的倍数,则p%mod余数为1



  • 分母p-1不是mod的倍数,则直接求快速幂加求分母的逆元(qmi(1-p,mod-2))即可




代码

#include
#include
using namespace std;
typedef long long LL;
const int mod = 9901;
int A, B;
//保存质因子以及出现的次数
unordered_map primes;
//试除法质因子分解
void divide(int n) {
for(int i = 2; i <= n / i; i++) {
if(n % i == 0) {
while(n % i == 0) {
primes[i]++;
n /= i;
}
}
}
if(n > 1) {
primes[n]++;
}
}
//快速幂
int qmid(int a, int b) {
int res = 1;
while(b) {
if(b & 1) res = (LL)res * a % mod;
a = (LL)a * a % mod;
b >>= 1;
}
return res;
}
int main(){
cin >> A >> B;
//对A分解质因子
divide(A);
int res = 1;
for(auto it : primes) {
//p是质因子,k是质因子的次数
int p = it.first, k = it.second * B;
// res要乘上每一项, 注意这里是k + 1
if((p - 1) % mod == 0) {
//不存在逆元,由于p - 1的是mod 的倍数, 故p % mod = 1
//所以1 + p + ... + p^k每个数%mod 都是1,共k + 1个数,总就是k + 1
res = (LL)res * (k + 1) % mod;
}
else{
res = (LL)res * (qmid(p, k + 1) - 1) % mod * qmid(p - 1, mod - 2) % mod;
}
}
if(!A) res = 0;
cout <<(res % mod + mod ) % mod < return 0;
}


推荐阅读
  • 本文介绍了一个来自AIZU ONLINE JUDGE平台的问题,即清洁机器人2.0。该问题来源于某次编程竞赛,涉及复杂的算法逻辑与实现技巧。 ... [详细]
  • 本文概述了在GNU/Linux系统中,动态库在链接和运行阶段的搜索路径及其指定方法,包括通过编译时参数、环境变量及系统配置文件等方式来控制动态库的查找路径。 ... [详细]
  • 本文提供了一个关于AC自动机(Aho-Corasick Algorithm)的详细解析与实现方法,特别针对P3796题目进行了深入探讨。文章不仅涵盖了AC自动机的基本概念,还重点讲解了如何通过构建失败指针(fail pointer)来提高字符串匹配效率。 ... [详细]
  • 本报告记录了嵌入式软件设计课程中的第二次实验,主要探讨了使用KEIL V5开发环境和ST固件库进行GPIO控制及按键响应编程的方法。通过实际操作,加深了对嵌入式系统硬件接口编程的理解。 ... [详细]
  • LoadRunner中的IP欺骗配置与实践
    为了确保服务器能够有效地区分不同的用户请求,避免多人使用同一IP地址造成的访问限制,可以通过配置IP欺骗来解决这一问题。本文将详细介绍IP欺骗的工作原理及其在LoadRunner中的具体配置步骤。 ... [详细]
  • 本文探讨了Java编程语言中常用的两个比较操作符==和equals方法的区别及其应用场景。通过具体示例分析,帮助开发者更好地理解和使用这两个概念,特别是在处理基本数据类型和引用数据类型的比较时。 ... [详细]
  • 本文详细介绍了PHP中的几种超全局变量,包括$GLOBAL、$_SERVER、$_POST、$_GET等,并探讨了AJAX的工作原理及其优缺点。通过具体示例,帮助读者更好地理解和应用这些技术。 ... [详细]
  • 本文介绍了用户界面(User Interface, UI)的基本概念,以及在iOS应用程序中UIView及其子类的重要性和使用方式。文章详细探讨了UIView如何作为用户交互的核心组件,以及它与其他UI控件和业务逻辑的关系。 ... [详细]
  • 本文探讨了线性表中元素的删除方法,包括顺序表和链表的不同实现策略,以及这些策略在实际应用中的性能分析。 ... [详细]
  • 实现Win10与Linux服务器的SSH无密码登录
    本文介绍了如何在Windows 10环境下使用Git工具,通过配置SSH密钥对,实现与Linux服务器的无密码登录。主要步骤包括生成本地公钥、上传至服务器以及配置服务器端的信任关系。 ... [详细]
  • 本文由chszs撰写,详细介绍了Apache Mina框架的核心开发流程及自定义协议处理方法。文章涵盖从创建IoService实例到协议编解码的具体步骤,适合希望深入了解Mina框架应用的开发者。 ... [详细]
  • LeetCode 102 - 二叉树层次遍历详解
    本文详细解析了LeetCode第102题——二叉树的层次遍历问题,提供了C++语言的实现代码,并对算法的核心思想和具体步骤进行了深入讲解。 ... [详细]
  • 解决UIScrollView自动偏移问题的方法
    本文介绍了一种有效的方法来解决在使用UIScrollView时出现的自动向下偏移的问题,通过调整特定的属性设置,可以确保滚动视图正常显示。 ... [详细]
  • 如何高效渲染JSON数据
    本文介绍了在控制器中返回JSON结果的方法,并详细说明了如何利用jQuery处理和展示这些数据,为Web开发提供了实用的技巧。 ... [详细]
  • Awk是一款功能强大的文本分析与处理工具,尤其在数据解析和报告生成方面表现突出。它通过读取由换行符分隔的记录,并按照指定的字段分隔符来划分和处理这些记录,从而实现复杂的数据操作。 ... [详细]
author-avatar
痴情季豪_726
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有