HDU 1452 Happy 2004(唯一分解定理)
2024-08-29 18:57:36
题目链接:传送门
题意:
求2004^x的全部约数的和。
分析:
由唯一分解定理可知
x=p1^a1*p2^a2*...*pn^an
那么其约数和 sum = (p1^0+p1^1^…+p1^a1)*…* (pn^0+pn^1^…+pn )
代码例如以下:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio> using namespace std; const int mod = 29; int quick_mod(int a,int b){
int ans = 1;
while(b){
if(b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
} int fac[10],cnt;
int num[10];
void init(){
int n = 2004;
cnt = 0;
memset(num,0,sizeof(num));
for(int i=2;i*i<=n;i++){
if(n%i==0){
fac[cnt]=i;
while(n%i==0) n/=i,num[cnt]++;
cnt++;
}
}
if(n>1) fac[cnt]=n,num[cnt++]=1;
} int main()
{
int n;
while(~scanf("%d",&n)&&n){
init();
int ans = 1;
for(int i=0;i<cnt;i++){
num[i]*=n;
int inv = quick_mod(fac[i]-1,mod-2);
ans=ans*((quick_mod(fac[i],num[i]+1)-1+mod)*inv%mod)%mod;
}
printf("%d\n",ans);
}
return 0;
}
最新文章
- javascript动画系列第三篇——碰撞检测
- java 的public private protected作用域
- Jesse Livermore的21句投机至理名言
- bootstrap源码分析之Carousel
- 【编程题目】查找最小的 k 个元素
- Linux网络管理
- linux 内核分析之list_head
- Linux下自动备份MySQL
- 【Linux】添加sudo用户、sudo用戶組
- 怎么知道我的laravel 是几版本的
- Linux 的特殊变量(2)
- 透析thinkphp5升级版开发框架tpframe
- 我花了 8 小时,";掌握";了一下 Flutter | Flutter 中文站上线
- sdk和api的区别
- STM32时钟
- (转载)Android开发——Android中常见的4种线程池(保证你能看懂并理解)
- 1月4日笔记 (vi编辑器)更新...
- mysql的级联复制和多源复制
- Swift中正则使用正则的几种方式
- wordpress防止网站被镜像四个方法