注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1225][HNOI2001] 求正整数  

2015-03-24 17:16:13|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1225: [HNOI2001] 求正整数

联动:http://www.lydsy.com/JudgeOnline/problem.php?id=3629
一样都是暴搜
不明白为啥有个DP标签

#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<iostream>
#include<cstring>
using namespace std;
int scan(){int i=0;scanf("%d",&i);return i;}
const int N = 1E5+10;
typedef long long ll;
short v[N];
int pri[N],n;
void getpri(){
int i,j;
for(i=2;i<=n;i++){
if(!v[i]){
pri[++pri[0]] = i;
}
for(j=1;j<=pri[0]&&i*pri[j]<=n;j++){
v[i*pri[j]]=1;
if(i%pri[j]==0)break;
}
}
}
//ll ans=2e18;
const int SIZE = 8000;
const int LEN = 10000;
struct Num{
int d[SIZE];
Num(ll x=0){
if(!x){d[(d[0]=1)]=0;return;}
for(d[0]=0;x;x/=LEN)d[++d[0]] = x%LEN;
}
void print(){
printf("%d",d[d[0]]);
for(int i=d[0]-1;i;i--)printf("%04d",d[i]);
}
}ans,now[5200];
ll tmp[SIZE];
Num operator * (const Num&a,const Num&b){
Num c;int i,j;c.d[0]=a.d[0]+b.d[0]+1;
for(i=1;i<=c.d[0];i++)tmp[i]=0;
for(i=1;i<=a.d[0];i++)
for(j=1;j<=b.d[0];j++){
tmp[i+j-1]+=a.d[i]*b.d[j];
}
for(i=1;i<=c.d[0];i++)
if(tmp[i]>=LEN){
tmp[i+1]+=tmp[i]/LEN;
tmp[i]%=LEN;
}
for(i=1;i<=c.d[0];i++)c.d[i]=tmp[i];
while(c.d[0]>1 && c.d[c.d[0]] == 0)c.d[0]--;
return c;
}
Num kpow(Num x,int k){
Num re=1;
for(;k;k/=2,x=x*x)
if(k&1)re=re*x;
return re;
}
bool operator < (const Num &a,const Num &b){
if(a.d[0]!=b.d[0])return a.d[0]<b.d[0];
for(int i=a.d[0];i;i--)
if(a.d[i]!=b.d[i])return a.d[i]<b.d[i];
return 1<1;
}
bool operator <=(const Num&a,const Num&b){return !(b<a);}
void dfs(int x=1,int left=n,int last=1e9){
if(ans<=now[x])return;
if(left==1){
ans = now[x];
return;
}
if(x>pri[0] || last==1)return;
for(int i=1;i<=last&&i<=left&&now[x]<ans;i++){
if(left%i==0){
now[x+1] = now[x];
dfs(x+1,left/i,i);
}
now[x]=now[x]*pri[x];
}
}
int main(){
//printf("%.2f",(double)sizeof(now)/1024/1024);
int i,j;
n = scan();
getpri();
//printf("%d %d\n",pri[0],pri[pri[0]]);
ans = kpow(2,n-1);
if(!v[n]){
ans.print();cout << endl;
}else{
now[1]=1;
dfs();
ans.print();cout << endl;
//cout << ans << endl;
}
return 0;
}


  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017