1,一个数n的过剩数定义为它的所有因子之和-2*n,小于0,设为-1
要求:返回一个区间的最大过剩数
2,解决:求出每个数的过剩数,rmq返回最大值.
难点:求出一个数的所有因子之和.
如果n的质因数分解为:n=p1^m1*p2^m2*...*pk^mk,
那么所有因子之和为:(1+p1+...+p1^m1)*...*(1+pk+...+pk^mk)
即:(p1^(m1+1)-1)/(p1-1)*...*(pk^(mk+1)-1)/(pk-1)
3,实现代码:
#include <iostream>
#include <cmath>
using namespace std;
#define MAX(x,y) (x > y ? x : y)
const int MAX=1025;
bool isPrime[MAX+1];
int total;//计数
int prime[MAX+1];
int c[MAX];//保存过剩数
//线性筛法寻找素数
void makePrime()
{
total=0;
memset(isPrime,true,sizeof(isPrime));
memset(prime,0,sizeof(prime));
for(int i=2;i<=MAX;i++)
{
if(isPrime[i]) prime[total++]=i;
for(int j=0; j<total && i*prime[j]<=MAX; j++)
{
isPrime[i*prime[j]]=false;
//i此时不是素数,只是拓展用
if(i%prime[j]==0) break;
}
}
}
int power(int x,int n)
{
int ret=1;
while(n--) ret*=x;
return ret;
}
int getNum(int d) //返回一个整数的过剩数
{
int tmp=d,m,sum=1;
for(int i=0;prime[i]*prime[i]<=tmp;i++)
{
if(tmp%prime[i]==0)
{
m=0;
while(tmp%prime[i]==0) m++,tmp/=prime[i];
sum*=(power(prime[i],m+1)-1)/(prime[i]-1);
}
}
if(tmp>1) sum*=(tmp+1);//k此时是一个素数
if(sum>d*2) return sum-d*2;
return -1;
}
int dp[MAX][18];
void makermq(int n,int b[])
{
int i,j;
for(i=0;i<n;i++)
dp[i][0]=b[i];
for(j=1;(1<<j)<=n;j++)
for(i=0;i+(1<<j)-1<n;i++)
dp[i][j]=MAX(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int rmq(int s,int v)
{
int k=(int)(log((v-s+1)*1.0)/log(2.0));
return MAX(dp[s][k],dp[v-(1<<k)+1][k]);
}
int main()
{
freopen("2.1.in","r",stdin);
makePrime();//生成质数表
memset(c,-1,sizeof(c));
for(int i=1;i<MAX;i++) //求出每个数的过剩数
c[i]=getNum(i);
makermq(MAX,c);
int cnt;
int x,y;
cin>>cnt;
while(cnt--)
{
cin>>x>>y;
cout<<rmq(x,y)<<endl;
}
return 0;
}
分享到:
相关推荐
国际大学生程序设计竞赛例题解.三:图论、动态规划算法、综合题专集
本系列丛书包括《ACM国际大学生程序设计竞赛:知识与入门》、《ACM国际大学生程序设计竞赛:算法与实现》、《ACM国际大学生程序设计竞赛:题目与解读》、《ACM国际大学生程序设计竞赛:比赛与思考》等4册,其中《ACM...
国际大学生程序设计竞赛例题解(六) 广东省大学生程序设计竞赛例题解析
第二本:国际大学生程序设计竞赛例题解 2 广东省大学生程序设计竞赛试题 2003-2005年 第三本:国际大学生程序设计竞赛例题解 3 图论·动态规划算法·综合题专集 第四本:国际大学生程序设计竞赛例题解 4 广东省...
此资源压缩包分为两卷,此卷为part1。 《ACM国际大学生程序设计竞赛:题目与解读》讲述了ACM国际大学生程序设计竞赛(ACM—...《ACM国际大学生程序设计竞赛:题目与解读》为各类算法配备经典例题及题库,并提供解题思路。
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
国际大学生程序设计竞赛例题解二,分享给大家!
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
国际大学生程序设计竞赛例题解.一:数论、计算几何、搜索算法专集.
国际大学生程序设计竞赛例题解 广东省大学生程序设计竞赛试题,搞ACM,信息学竞赛的同学都用得着!
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
为了帮助高等院校的大学生们备战国际大学生程序设计竞赛,帮助他们提高程序设计水平和培养更强的分析问题和解决问题的能力,我们编写了这本辅导教材。本书所用的语言是Pascal(Delphi)。全书共分六章,第1章先介绍...
中国大学生数学建模竞赛题解_matlab
此资源压缩包分为两卷,此卷为part2。 《ACM国际大学生程序设计竞赛:题目与解读》讲述了ACM国际大学生程序设计竞赛(ACM—...《ACM国际大学生程序设计竞赛:题目与解读》为各类算法配备经典例题及题库,并提供解题思路。
国际大学生程序设计竞赛(ACM)例题解析合集八本1-8,设计到各类算法的方方面面,包括动态规划、图论、搜索算法等。对于做算法开发的程序员很有参考意义。 附件为百度网盘永久链接地址。
国际大学生程序设计竞赛例题解 6 广东省大学生程序设计竞赛试题解 2008-2009年 郭嵩山 电子工业出版社
国际大学生程序设计竞赛例题解赛试题(一)