任意门:http://poj.org/problem?id=1845、
Sumdiv
Time Limit: 1000MS |
Memory Limit: 30000K |
|
Total Submissions: 30268 |
Accepted: 7447 |
Description
Input
Output
Sample Input
2 3
Sample Output
15
Hint
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 【二分 || 逆元】的更多相关文章
-
POJ 1845 Sumdiv 【逆元】
题意:求A^B的所有因子之和 很容易知道,先把分解得到,那么得到,那么 的所有因子和的表达式如下 第一种做法是分治求等比数列的和 用递归二分求等比数列1+pi+pi^2+pi^3+...+pi^n: ...
-
POJ 1845 Sumdiv(逆元)
题目链接:Sumdiv 题意:给定两个自然数A,B,定义S为A^B所有的自然因子的和,求出S mod 9901的值. 题解:了解下以下知识点 1.整数的唯一分解定理 任意正整数都有且只有唯一的方式 ...
-
poj 1845 POJ 1845 Sumdiv 数学模板
筛选法+求一个整数的分解+快速模幂运算+递归求计算1+p+p^2+````+p^nPOJ 1845 Sumdiv求A^B的所有约数之和%9901 */#include<stdio.h>#i ...
-
POJ 1845 Sumdiv#质因数分解+二分
题目链接:http://poj.org/problem?id=1845 关于质因数分解,模板见:http://www.cnblogs.com/atmacmer/p/5285810.html 二分法思想 ...
-
poj 1845 Sumdiv (等比求和+逆元)
题目链接:http://poj.org/problem?id=1845 题目大意:给出两个自然数a,b,求a^b的所有自然数因子的和模上9901 (0 <= a,b <= 50000000 ...
-
POJ 1845 Sumdiv(因子分解+快速幂+二分求和)
题意:给你A,B,让求A^B所有的因子和模上9901 思路:A可以拆成素因子的乘积: A = p1^x1 * p2^x2 *...* pn^xn 那么A^B = p1^(B*x1) * p2^(B*x ...
-
POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]
传送门:http://poj.org/problem?id=1845 大致题意: 求A^B的所有约数(即因子)之和,并对其取模 9901再输出. 解题基础: 1) 整数的唯一分解定理: 任意正整数都有 ...
-
POJ 1845 Sumdiv(求因数和 + 逆元)题解
题意:给你a,b,要求给出a^b的因子和取模9901的结果. 思路:求因子和的方法:任意A = p1^a1 * p2^a2 ....pn^an,则因子和为sum =(1 + p1 + p1^2 + . ...
-
poj 1845 Sumdiv(约数和,乘法逆元)
题目: 求AB的正约数之和. 输入: A,B(0<=A,B<=5*107) 输出: 一个整数,AB的正约数之和 mod 9901. 思路: 根据正整数唯一分解定理,若一个正整数表示为:A= ...
随机推荐
-
Redis集群案例与场景分析
1.背景 Redis的出现确实大大地提高系统大并发能力支撑的可能性,转眼间Redis的最新版本已经是3.X版本了,但我们的系统依然继续跑着2.8,并很好地支撑着我们当前每天5亿访问量的应用系统.想当年 ...
-
Lua 学习笔记(一)环境搭建
Lua是一个小巧的脚本语言.Lua由标准C编写而成,代码简洁,几乎在所有的操作系统和平台上都可以编译,运行. 主要讲一下mac和win下的环境搭建. 工具: 1.Sublime Text 2 ...
-
一些比较好的shellscript脚本
1. 变量与替换 #!/bin/bash # 变量替换 # 另外, 变量替换还有许多别的语法 # 例如, b=${a/23/bb} 将 23 替换成 bb 等等, 用到时再找 a=375 hello= ...
-
shell/bash 让vi/vim显示空格,及tab字符
shell/bash 让vi/vim显示空格,及tab字符 Vim 可以用高亮显示空格和TAB.文件中有 TAB 键的时候,你是看不见的.要把它显示出来::set listTAB 键显示为 ^I, ...
-
Cocos2dx 学习笔记整理----开发环境搭建
最近在学习cocos2dx,预备将学习过程整理成笔记. 需要的工具和环境整理一下: 使用的版本 cocos2dx目前已经出到了v3.1.1,学习和项目的话还是用2.2.3为宜,毕竟不大想做小白鼠,并且 ...
-
shiro真正项目中的实战应用核心代码!!!
欢迎转载!!!请注明出处!!! 说道shiro的学习之路真是相当坎坷,网上好多人发的帖子全是简单的demo样例,核心代码根本没有,在学习过程中遇到过N多坑. 经过自己的努力,终于整出来了,等你整明白之 ...
-
session 与 cookie (一)
服务器信息临时存储 session篇 web.xml设置 <session-config> <session-timeout></session-timeout> ...
-
安装SQl Server 报错 ";需要 Microsoft.NET Framework 3.5 ServicePack 1"; 解决方法
前言 之前装Sql Server都没遇到过这样的问题, 昨天重装了系统之后, 然后安装SQl Server 报错,提示 "需要 Microsoft.NET Framework 3.5 Ser ...
-
Docker学习之1—基础及安装
Docker介绍: Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化.容器是完全使用沙箱机制 ...
-
CDH 6.0.1 集群搭建 「Before install」
从这一篇文章开始会有三篇文章依次介绍集群搭建 「Before install」 「Process」 「After install」 继上一篇使用 docker 部署单机 CDH 的文章,当我们使用 d ...