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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2705][SDOI2012]Longge的问题  

2014-10-13 11:47:59|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
又是数学题……
按照惯例题解在代码下方

#include<cstdio>
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
LL n,m;
LL list[2][N],ylist[N];
int num[2][N];
map<LL,LL>f;
//int f[N];
LL scan(){LL i=0;cin>>i;return i;}
int gcd(int a,int b){return a?gcd(b%a,a):b;}
void get(LL x,LL a[],int b[]){
a[0] = 0;
for(int i=2;(long long)i*i<=x;i++)
if(x%i==0){
a[++a[0]] = i;
b[a[0]] = 0;
while(x%i==0)
b[a[0]]++,x/=i;
}
if(x > 1){a[++a[0]] = x;b[a[0]]=1;}
}
void mlist(int x=1,LL now=1,int type=0,LL val=1){
if(x > list[type][0]){
if(!type){
ylist[++ylist[0]] = now;
}else{
if(now!=ylist[val])
f[now] -= f[ylist[val]];
}
return;
}
LL tmp = 1;
for(int i=0;i<=num[type][x];i++){
mlist(x+1,now*tmp,type,val);
tmp *= list[type][x];
}
}
int main(){
int i,j;
n = scan();
get(n,list[0],num[0]);
mlist();
sort(ylist+1,ylist+1+ylist[0]);
LL ans=0;
for(i=ylist[0];i;i--){
f[ylist[i]] += n/ylist[i];
ans += (f[ylist[i]])*ylist[i];
if(i==1)break;
get(ylist[i],list[1],num[1]);
mlist(1,1,1,i);
}
cout<<ans<<endl;
return 0;
}

题解:
容斥原理(不是很标准的那种)。
先找到n的所有约数,然后容斥原理统计这个数作为gcd(i,n)出现了几次。
做法和之前做过的一道NOI能量采集很像……似乎因为太颓了没发题解?
map大法好
另:好像之前谁和我说可以用phi函数来做?
去百度了一下,有这样一个性质j = gcd(i,n)的个数为phi(n/j)
之前也想过能不能这么做但是因为感觉是错的所以没敢用- -|
  评论这张
 
阅读(66)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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