POJ 1845 Sumdiv 【二分 || 逆元】

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

任意门:http://poj.org/problem?id=1845

Sumdiv

Time Limit: 1000MS

Memory Limit: 30000K

Total Submissions: 30268

Accepted: 7447

Description

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

Input

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

Output

The only line of the output will contain S modulo 9901.

Sample Input

2 3

Sample Output

15

Hint

2^3 = 8. 
The natural divisors of 8 are: 1,2,4,8. Their sum is 15. 
15 modulo 9901 is 15 (that should be output). 

Source

题目概括:

给出 A 和 B ,求 AB 所有因子之和,答案 mod 9901;

解题思路:

可对 A 先进行素因子分解 A = p1a1 * p2a2 * p3a3 * ...... * pnan

即 AB = p1a1*B * p2a2*B * p3a3*B * ...... * pnan*B

那么 AB 所有因子之和 = (1 + P11 + P12 + P13 + ... + P1a1*B) *  (1 + P21 + P22 + P23 + ... + P2a2*B) * ......* (1 + Pn1 + Pn2 + Pn3 + ... + Pnan*B) ;

对于  (1 + P1 + P2 + P3 + ... + Pa1*B) 我们可以

①二分求和 (47 ms)

AC code:

 #include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const LL MOD = ;
const int MAXN = 1e4+;
LL p[MAXN];
bool isprime[MAXN];
int cnt;
LL A, B; void init() //打表预处理素因子
{
cnt = ;
memset(isprime, , sizeof(isprime));
for(LL i = ; i < MAXN; i++){
if(isprime[i]){
p[cnt++] = i;
for(int j = ; j < cnt && p[j]*i < MAXN; j++)
isprime[p[j]*i] = false;
}
}
} LL qpow(LL x, LL n)
{
LL res = 1LL;
while(n){
if(n&) res = (res%MOD*x%MOD)%MOD;
x = (x%MOD*x%MOD)%MOD;
n>>=1LL;
}
return res;
} LL sum(LL x, LL n)
{
if(n == ) return ;
LL res = sum(x, (n-)/);
if(n&){
res = (res + res%MOD*qpow(x, (n+)/)%MOD)%MOD;
}
else{
res = (res + res%MOD*qpow(x, (n+)/)%MOD)%MOD;
res = (res + qpow(x, n))%MOD;
}
return res;
} int main()
{
LL ans = ;
scanf("%lld %lld", &A, &B);
init();
//printf("%d\n", cnt);
for(LL i = ; p[i]*p[i] <= A && i < cnt; i++){ //素因子分解
//printf("%lld\n ", p[i]);
if(A%p[i] == ){
LL num = ;
while(A%p[i] == ){
num++;
A/=p[i];
}
ans = ((ans%MOD*sum(p[i], num*B)%MOD)+MOD)%MOD;
}
}
if(A > ){
// puts("zjy");
ans = (ans%MOD*sum(A, B)%MOD+MOD)%MOD;
} printf("%lld\n", ans); return ;
}

②应用等比数列求和公式 ( 0ms )

因为要保证求模时的精度,所以要求逆元。

这里用的方法是一般情况都适用的 : A/B mod p = A mod (p*B) / B;

但是考虑乘法会爆int,所以自定义一个二分乘法。

AC code:

 // 逆元 + 二分乘法
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int MAXN = 1e4+;
const LL mod = ;
int p[MAXN], cnt;
bool isp[MAXN];
LL A, B; void prime()
{
memset(isp, , sizeof(isp));
isp[] = isp[] = false;
for(int i = ; i < MAXN; i++){
if(isp[i]){
p[cnt++] = i;
for(int k = ; k < cnt && i*p[k] < MAXN; k++){
isp[i*p[k]] = false;
}
}
}
} LL mutil(LL x, LL y, LL MOD)
{
LL res = ;
while(y){
if(y&) res = (res+x)%MOD;
x = (x+x)%MOD;
y>>=1LL;
}
return res;
} LL q_pow(LL x, LL n, LL MOD)
{
LL res = 1LL;
while(n){
if(n&) res = mutil(res, x, MOD)%MOD;
x = mutil(x, x, MOD)%MOD;
n>>=1LL;
}
return res;
} int main()
{
LL num = ;
LL ans = ;
scanf("%lld %lld", &A, &B);
prime();
for(int i = ; p[i]*p[i] <= A; i++){
if(A%p[i] == ){
num = ;
while(A%p[i] == ){
A/=p[i];
num++;
}
LL m = mod*(p[i]-);
ans *= (q_pow(p[i], num*B+, m) + m-)/(p[i] - );
ans = ans%mod;
//ans += ((q_pow(p[i], num*B, mod*(p[i]-1))-p[i])/(p[i]-1))%mod;
}
} if(A != ){
// ans += ((q_pow(A, B, mod*(A-1))-A)/(A-1))%mod;
LL m = mod*(A-);
ans*=(q_pow(A, B+, m)+m-)/(A-);
ans = ans%mod;
} printf("%lld\n", ans); return ;
}

POJ 1845 Sumdiv 【二分 || 逆元】的更多相关文章

  1. POJ 1845 Sumdiv 【逆元】

    题意:求A^B的所有因子之和 很容易知道,先把分解得到,那么得到,那么 的所有因子和的表达式如下 第一种做法是分治求等比数列的和  用递归二分求等比数列1+pi+pi^2+pi^3+...+pi^n: ...

  2. POJ 1845 Sumdiv(逆元)

    题目链接:Sumdiv 题意:给定两个自然数A,B,定义S为A^B所有的自然因子的和,求出S mod 9901的值. 题解:了解下以下知识点   1.整数的唯一分解定理 任意正整数都有且只有唯一的方式 ...

  3. poj 1845 POJ 1845 Sumdiv 数学模板

    筛选法+求一个整数的分解+快速模幂运算+递归求计算1+p+p^2+````+p^nPOJ 1845 Sumdiv求A^B的所有约数之和%9901 */#include<stdio.h>#i ...

  4. POJ 1845 Sumdiv&num;质因数分解&plus;二分

    题目链接:http://poj.org/problem?id=1845 关于质因数分解,模板见:http://www.cnblogs.com/atmacmer/p/5285810.html 二分法思想 ...

  5. poj 1845 Sumdiv &lpar;等比求和&plus;逆元&rpar;

    题目链接:http://poj.org/problem?id=1845 题目大意:给出两个自然数a,b,求a^b的所有自然数因子的和模上9901 (0 <= a,b <= 50000000 ...

  6. POJ 1845 Sumdiv&lpar;因子分解&plus;快速幂&plus;二分求和&rpar;

    题意:给你A,B,让求A^B所有的因子和模上9901 思路:A可以拆成素因子的乘积: A = p1^x1 * p2^x2 *...* pn^xn 那么A^B = p1^(B*x1) * p2^(B*x ...

  7. POJ 1845 Sumdiv &lbrack;素数分解 快速幂取模 二分求和等比数列&rsqb;

    传送门:http://poj.org/problem?id=1845 大致题意: 求A^B的所有约数(即因子)之和,并对其取模 9901再输出. 解题基础: 1) 整数的唯一分解定理: 任意正整数都有 ...

  8. POJ 1845 Sumdiv(求因数和 &plus; 逆元)题解

    题意:给你a,b,要求给出a^b的因子和取模9901的结果. 思路:求因子和的方法:任意A = p1^a1 * p2^a2 ....pn^an,则因子和为sum =(1 + p1 + p1^2 + . ...

  9. poj 1845 Sumdiv(约数和,乘法逆元)

    题目: 求AB的正约数之和. 输入: A,B(0<=A,B<=5*107) 输出: 一个整数,AB的正约数之和 mod 9901. 思路: 根据正整数唯一分解定理,若一个正整数表示为:A= ...

随机推荐

  1. Redis集群案例与场景分析

    1.背景 Redis的出现确实大大地提高系统大并发能力支撑的可能性,转眼间Redis的最新版本已经是3.X版本了,但我们的系统依然继续跑着2.8,并很好地支撑着我们当前每天5亿访问量的应用系统.想当年 ...

  2. Lua 学习笔记(一)环境搭建

    Lua是一个小巧的脚本语言.Lua由标准C编写而成,代码简洁,几乎在所有的操作系统和平台上都可以编译,运行. 主要讲一下mac和win下的环境搭建. 工具:      1.Sublime Text 2 ...

  3. 一些比较好的shellscript脚本

    1. 变量与替换 #!/bin/bash # 变量替换 # 另外, 变量替换还有许多别的语法 # 例如, b=${a/23/bb} 将 23 替换成 bb 等等, 用到时再找 a=375 hello= ...

  4. shell&sol;bash 让vi&sol;vim显示空格&comma;及tab字符

    shell/bash 让vi/vim显示空格,及tab字符 Vim 可以用高亮显示空格和TAB.文件中有 TAB 键的时候,你是看不见的.要把它显示出来::set listTAB 键显示为 ^I,   ...

  5. Cocos2dx 学习笔记整理----开发环境搭建

    最近在学习cocos2dx,预备将学习过程整理成笔记. 需要的工具和环境整理一下: 使用的版本 cocos2dx目前已经出到了v3.1.1,学习和项目的话还是用2.2.3为宜,毕竟不大想做小白鼠,并且 ...

  6. shiro真正项目中的实战应用核心代码!!!

    欢迎转载!!!请注明出处!!! 说道shiro的学习之路真是相当坎坷,网上好多人发的帖子全是简单的demo样例,核心代码根本没有,在学习过程中遇到过N多坑. 经过自己的努力,终于整出来了,等你整明白之 ...

  7. session 与 cookie (一)

    服务器信息临时存储 session篇 web.xml设置 <session-config> <session-timeout></session-timeout> ...

  8. 安装SQl Server 报错 &quot&semi;需要 Microsoft&period;NET Framework 3&period;5 ServicePack 1&quot&semi; 解决方法

    前言 之前装Sql Server都没遇到过这样的问题, 昨天重装了系统之后, 然后安装SQl Server 报错,提示 "需要 Microsoft.NET Framework 3.5 Ser ...

  9. Docker学习之1—基础及安装

    Docker介绍: Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化.容器是完全使用沙箱机制 ...

  10. CDH 6&period;0&period;1 集群搭建 「Before install」

    从这一篇文章开始会有三篇文章依次介绍集群搭建 「Before install」 「Process」 「After install」 继上一篇使用 docker 部署单机 CDH 的文章,当我们使用 d ...