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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2749][HAOI2012]外星人  

2014-12-15 21:50:13|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2749: [HAOI2012]外星人

想了差不多1h……想错两次……
最后就差一步就想出来,但是还是没能想出来QAQ
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1E5+10;
typedef long long ll;
int n;
ll f[N];
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
bool get(int x,ll &re){
bool ok=0;
for(int i=2;i*i<=x;i++)
if(x%i==0){
ok=1;
int cot=0;
while(x%i==0)cot++,x/=i;
re += f[i]*cot;
}
if(x > 1 && ok){
re += f[x];
}
return ok;
}
int main(){
int i,j,a,b,MVAL = 1e5;
//pre make
f[2] = 1;
for(i=3;i<=MVAL;i++)if(!get(i,f[i]))f[i] = f[i-1];
//printf("[%d]\n",f[5]);
int nn = scan();
//requery
while(nn--){
n = scan();
//for(i=1;i<=MVAL;i++)f[i] = 0;
ll ans=0;
bool ok=0;
for(i=1;i<=n;i++){
a = scan();b = scan();
ans += f[a]*b;
if(a == 2)ok=1;
}
if(!ok)ans ++;
cout << ans << endl;
}
return 0;
}

题解:
首先根据题目下的提示知道,每次求phi就相当于把所以Pi^Ai -> (Pi-1)*Pi^(Ai-1)
可以得到模拟的方法,每次按照这个规则对所有Pi进行变换,直到都变成1,注意每次新生成的(Pi-1)要分解质因数
想办法用数据维护啊什么的,发现一个数最后可能被分成乱七八糟的一大堆……没法搞
可以注意到对于所有Pi>2每产生一个Pi-1,必然会分解出来一个2。
这样的话就会产生一堆2,并且每次操作都在不断地产生2。
直接统计最后会分解出多少2就行了,开始前预处理出一个f[i]表示i会分解出多少2.
注意特判一开始没有2的情况
  评论这张
 
阅读(129)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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