POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]

时间:2022-01-31 00:23:17

传送门:http://poj.org/problem?id=1845

大致题意:

求A^B的所有约数(即因子)之和,并对其取模 9901再输出。

解题基础:

1) 整数的唯一分解定理

任意正整数都有且只有一种方式写出其素因子的乘积表达式。

POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列],其中POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]为素数

2) 约数和公式

对于已经分解的整数POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列],A的所有因子之和为POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]

3) 同余模公式

(a+b)%m=(a%m+b%m)%m

(a*b)%m=(a%m*b%m)%m

1: 对A进行素因子分解

这里如果先进行筛50000内的素数会爆空间,只能用最朴素的方法进行分解

2:A^B的所有约数之和为

POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]

3: 求2中的等比序列

由于给的数据量大,肯定不能直接用等比序列的求和公式,要用分治法进行求解

POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]

一直对POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]递归求解

S的下标为偶数类比一下

4:反复平方法计算幂次式POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]

一个快速幂取模的板子,直接套上

#include<iostream>
#include<string.h>
#include<cstdio>
using namespace std;
int p[10000];
int q[10000];
const int mod = 9901;
//快速幂取模板子
long long qucick_pow(int m, int n, int moD)
{
if(n == 0)
return 1;
long long x = qucick_pow(m, n / 2, moD);
long long ans = x * x % mod;
if(n % 2)
ans = ans * m % mod;
return ans;
}
// 递归求解等比数列
long long sum(int m, int n)
{
if(n == 0)
return 1;
if(n % 2)
{
return (sum(m, n / 2) * (1 + qucick_pow(m, n / 2 + 1, mod))) % mod;
}
else
{
return (sum(m, n / 2 - 1) * (1 + qucick_pow(m, n / 2 + 1, mod)) + qucick_pow(m, n / 2, mod)) % mod;
}
}
int main()
{
int a, b;
scanf("%d %d", &a, &b);
int cnt = 0;
for(int i=2;i*i<=a;)
{
if(a%i==0)
{
p[cnt]=i;
while(a%i==0)
{
a/=i;
q[cnt]++;
}
cnt++;
}
if(i==2)
i+=1;
else
i+=2;
}
if(a!=1)
p[cnt]=a,q[cnt++]=1;
long long ans = 1;
for(int i = 0; i < cnt; i++)
{
ans = (ans * (sum(p[i], q[i] * b) % mod)) % mod;
}
cout << ans % mod << endl;
}

POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]的更多相关文章

  1. POJ 3233-Matrix Power Series&lpar; S &equals; A &plus; A&Hat;2 &plus; A&Hat;3 &plus; … &plus; A&Hat;k 矩阵快速幂取模&rpar;

    Matrix Power Series Time Limit: 3000MS   Memory Limit: 131072K Total Submissions: 20309   Accepted:  ...

  2. 快速幂取模&lpar;POJ 1995&rpar;

    http://poj.org/problem?id=1995 以这道题来分析一下快速幂取模 a^b%c(这就是著名的RSA公钥的加密方法),当a,b很大时,直接求解这个问题不太可能 利用公式a*b%c ...

  3. HDU--杭电--4506--小明系列故事——师兄帮帮忙--快速幂取模

    小明系列故事——师兄帮帮忙 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) To ...

  4. 【转】C语言快速幂取模算法小结

    (转自:http://www.jb51.net/article/54947.htm) 本文实例汇总了C语言实现的快速幂取模算法,是比较常见的算法.分享给大家供大家参考之用.具体如下: 首先,所谓的快速 ...

  5. HDU 1061 Rightmost Digit --- 快速幂取模

    HDU 1061 题目大意:给定数字n(1<=n<=1,000,000,000),求n^n%10的结果 解题思路:首先n可以很大,直接累积n^n再求模肯定是不可取的, 因为会超出数据范围, ...

  6. UVa 11582 &lpar;快速幂取模&rpar; Colossal Fibonacci Numbers&excl;

    题意: 斐波那契数列f(0) = 0, f(1) = 1, f(n+2) = f(n+1) + f(n) (n ≥ 0) 输入a.b.n,求f(ab)%n 分析: 构造一个新数列F(i) = f(i) ...

  7. POJ3641-Pseudoprime numbers(快速幂取模)

    题目大意 判断一个数是否是伪素数 题解 赤果果的快速幂取模.... 代码: #include<iostream> #include<cmath> using namespace ...

  8. 九度OJ 1085 求root&lpar;N&comma; k&rpar; -- 二分求幂及快速幂取模

    题目地址:http://ac.jobdu.com/problem.php?pid=1085 题目描述: N<k时,root(N,k) = N,否则,root(N,k) = root(N',k). ...

  9. CodeForces Round &num;191 &lpar;327C&rpar; - Magic Five 等比数列求和的快速幂取模

    很久以前做过此类问题..就因为太久了..这题想了很久想不出..卡在推出等比的求和公式,有除法运算,无法快速幂取模... 看到了 http://blog.csdn.net/yangshuolll/art ...

随机推荐

  1. Android之输入框光标和Hint的位置

    如图所示,要实现这一的需求,一般人的布局方式就是左边一button,右边一button,中间一个EditText,为了输入框的响应触摸范围更大往往不会把宽度设置为wrap_content,要么设置成m ...

  2. 过滤菜鸟的iOS面试题-b

    网上已经有很多针对各种知识点的面试题,面试时有些人未必真正理解也能通过背题看上去很懂.我自己总结了4道面试题,好快速的判断这个人是否是一个合格的工程师,欢迎大家点评. 1.struct和class的区 ...

  3. Samba服务器

    Windows操作系统下:DOC命令下:netstat -an查看端口 (一)简介 文件服务器 (二)端口 smbd: 为clinet提高资源访问 tcp  139  445    (类似于windo ...

  4. XSS攻击及预防

    跨站脚本攻击(Cross Site Scripting),为不和层叠样式表(Cascading Style Sheets, CSS)的缩写混淆,故将跨站脚本攻击缩写为XSS.恶意攻击者往Web页面里插 ...

  5. 1,入门-Hello Soring Boot

    什么是SpringBoot Spring Boot是Spring社区发布的一个开源项目,旨在帮助开发者快速并且更简单的构建项目.大多数SpringBoot项目只需要很少的配置文件. SpringBoo ...

  6. border-sizing属性

    box-sizing属性可以为三个值之一:content-box(default),border-box,padding-box. content-box,border和padding不计算入widt ...

  7. Asp&period;net Core 跨域配置

    一般情况WebApi都是跨域请求,没有设置跨域一般会报以下错误 No 'Access-Control-Allow-Origin' header is present on the requested ...

  8. vue jquery js 获取当前时间本周的第一天 和 本月的第一天

    交互的时候传输数据 后台要求这样的数据 直接上代码 这是我找度姨要的  附上链接  https://www.cnblogs.com/wasabii/p/7756560.html 它里面有本季度第一天  ...

  9. 用户身份切换之初窥企业远程用户没root还有root权限

    一直很困扰我,既然企业不让用root不能登录,那怎么操作文件呢? 原来...... su -    用来切换初始变量 $PATH $HOME等 sudo 用的时候会su到root需要root的密码,这 ...

  10. 【从0到1学Web前端】CSS伪类和伪元素 分类: HTML&plus;CSS 2015-06-02 22&colon;29 1065人阅读 评论&lpar;0&rpar; 收藏

    1.CSS中的伪类 CSS 伪类用于向某些选择器添加特殊的效果. 语法: selector : pseudo-class {property: value} CSS 类也可与伪类搭配使用 select ...