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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1220][HNOI2002]跳蚤  

2014-10-07 16:09:58|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1220: [HNOI2002]跳蚤

最近不知为啥越来越懒了
好长时间没来blog感觉都要长草了……(反正也没几个人来看吧
一道数学题。
我数学不好看了好几份题解才搞明白╮(╯﹏╰)╭
按照惯例题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
int scan(){int i = 0;scanf("%d",&i);return i;}
int n,m,pri[(int)1e5];
int phi(int nn){
int re=1;
for(int i=2;(long long)i*i <= nn;i++)
if(nn%i ==0){
pri[++pri[0]] = i;
re*=i-1;nn/=i;
while(nn%i==0)
re*=i,nn/=i;
}
if(nn > 1)re*=nn-1,pri[++pri[0]] = nn;
return re;
}
const int LEN = 500;
const int BIT = 10000;
struct BIG{
int d[LEN];
BIG(){memset(d,0,sizeof(d));d[0] = 1;}
BIG(int a){*this = BIG();if(!a)return;for(d[0] = 0;a;a/=BIT)d[++d[0]] = a%BIT;}
void print(){printf("%d",d[d[0]]);for(int i=d[0]-1;i;i--)printf("%04d",d[i]);}
};
typedef BIG Big;
Big add,sub,tmp;
BIG operator + (BIG a,BIG b){
BIG c;
c.d[0] = max(a.d[0],b.d[0])+1;
for(int i=1;i<=c.d[0];i++){
c.d[i] += a.d[i] + b.d[i];
if(c.d[i] >= BIT){
c.d[i+1] += c.d[i]/BIT;
c.d[i] %= BIT;
}
}
while(c.d[0] > 1 && c.d[c.d[0]]==0)c.d[0]--;
return c;
}
BIG operator - (BIG a,BIG b){
BIG c;
c.d[0] = max(a.d[0],b.d[0]);
for(int i=1;i<=c.d[0];i++){
c.d[i] += a.d[i] - b.d[i];
if(c.d[i] < 0){
c.d[i+1]--;
c.d[i]+=BIT;
}
}
while(c.d[0] > 1 && c.d[c.d[0]]==0)c.d[0]--;
return c;
}
BIG operator * (BIG &a,BIG &b){
BIG c;
c.d[0] = a.d[0] + b.d[0] + 1;
for(int i=1;i<=a.d[0];i++)
for(int j=1;j<=b.d[0];j++)
c.d[i+j-1]+= a.d[i]*b.d[j];
for(int i=1;i<=c.d[0];i++)
if(c.d[i] >= BIT){
c.d[i+1]+=c.d[i]/BIT;
c.d[i]%=BIT;
}
while(c.d[0] > 1 && c.d[c.d[0]]==0)c.d[0]--;
return c;
}
Big pow(Big x,int k){
Big re = Big(1);
for(;k;x=x*x,k/=2)
if(k&1)re=re*x;
return re;
}
int main(){
int i,j,pn,bn,l;
n = scan();m = scan();
pn = phi(m);
bn = 1<<pri[0];
for(i=0;i<bn;i++){
int ii = i,cot=0;
l = 1;
for(j=1;ii;j++,ii/=2)if(ii&1)l = l*pri[j],cot++;
if(cot&1) sub = sub + pow(Big(m/l),n);
else add = add + pow(Big(m/l),n);
}
tmp = add - sub;
tmp.print();
return 0;
}

题解:
能走到自己左边的一位的的要求是卡片上n+1个数的gcd为1
因为卡片上必然有一个m,所以统计一下含有与m互质的数的卡片个数
直接统计没法统计,考虑用总的减去不含的个数
不含的个数用容斥原理计算,比如全含某一个因子的数的卡片个数 = (m/a)^n
需要先m^0.5分解质因数
(这个地方我想了好久)
我代码i是从0开始的,所以就相当于容斥原理做完之后又用总的减去了
  评论这张
 
阅读(104)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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