LOJ #124. 除数函数求和 1
2024-08-29 00:34:45
题目描述
$\sigma_k(n) = \sum_{d | n} d ^ k$
求 $\sum_{i=1}^n\sigma_k(i)$ 的值对 109 取模的结果。
输入格式
第一行两个正整数 n,k 。
输出格式
第一行输出答案。
样例
输入样例
5 2
输出样例
63
数据范围与提示
对于 100% 的数据,1≤n,k≤1077 。
Solution:
本题ZYYS。。。
直接枚举显然不行,我们考虑改为求$n$的某一因子$d$在整个函数中的贡献是多少。
套上数论分块的思想,一个因子$d$对式子的贡献是$\lfloor{\frac{n}{d}}\rfloor\times d^k$。
这样我们需要处理的就是$d^k$,直接$O(n\log k)$快速幂求出每个因子的幂是肯定不行的,因为$n$是$10^7$,直接会T。
那么还是考虑优化,我们发现,每个数都能唯一分解,而在求幂时会有重复计算的质因子幂。于是,我们考虑线筛,这样就可以用每个数的最小质因子幂去算它的幂了,那么整个过程只会对$n\leq 10^7$内的质数进行快速幂,最后复杂度就成了$\sqrt n \log k$,完全可行。
所以最后就只需再$O(n)$扫一遍因子累加贡献求和就好了。
代码:
#include<iostream>
#define il inline
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)>(b)?(b):(a)) using namespace std;
const int N=1e7,mod=1e9+;
int prime[N+],ans,cnt,n,k,sum[N+];
bool isprime[N+]; il int fast(ll s,ll k){
ll ans=;
while(k){
if(k&)ans=ans*s%mod;
k>>=;
s=s*s%mod;
}
return ans;
} il void init(){
sum[]=;
For(i,,n+) {
if(!isprime[i]) prime[++cnt]=i,sum[i]=fast(i,k);
for(int j=;j<=cnt&&prime[j]*i<=n+;j++){
isprime[prime[j]*i]=;
sum[prime[j]*i]=sum[i]*1ll*sum[prime[j]]%mod;
if(i%prime[j]==)break;
}
}
} int main(){
ios::sync_with_stdio();
cin>>n>>k;
init();
For(i,,n) ans=(ans+1ll*(n/i)*sum[i])%mod;
cout<<ans;
return ;
}
最新文章
- Guass列选主元消去法和三角分解法
- 吐槽贴:百度地图 api 封装 的实用功能 [源码下载]
- Java Service Wrapper简介与使用
- WebApi深入学习--概述+路由查找
- AC自动机——Uva 11468 子串
- VS下的解决方案目录结构设置和管理
- 转评:你造promise就是monad吗
- 越狱Season 1-Episode 4: Cute Poison
- Android——requestWindowFeature
- android学习日记25--ANR和Hander消息机制
- 树莓派安装mjpg-streamer视频监控 分类: Raspberry Pi 2015-04-12 23:41 144人阅读 评论(0) 收藏
- 『邪恶のWIFI』搭建假冒WIFI热点等女神来蹭网啊 - -。
- pygame系列_游戏窗口显示策略
- C#压缩文件夹坑~
- bzoj3527: [Zjoi2014]力 fft
- 测试CentOS-7-x86_64-Minimal-1708.iso这种光盘安装效果
- three.js 3d三维网页代码加密的实现方法
- LeetCode 任务调度器-Python3<;八>;
- maven插件 按配置加载不同环境配置文件进行打包(maven-war-plugin)
- node.js 笔记一
热门文章
- eclipse环境Dynamic web module version 3.1版本的进步,简化Dynamic web object 中Servlet类的配置,不用web.xml配置<;Servlet>;
- 解决Cannot reinitialise DataTable问题 解决dataTables再次调用不能清空数据
- 用python写一个类似于linux中的tree
- redis源代码结构解析
- C# 禁止在textBox输入框输入非法字符
- python基础之内置函数补充、匿名函数、递归函数
- Python数据挖掘-航空公司客户价值分析
- Android 使用RxJava实现一个发布/订阅事件总线
- 9path 导致的一场冤假错案
- Hadoop 原理总结