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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1951][Sdoi2010]古代猪文  

2014-10-21 17:32:42|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1951: [Sdoi2010]古代猪文

题目描述就是一坨翔……

大致就是求G^Sigma{C(N, i ),i | N} mod M的值,其中M = 999911659。

算是新学算法

本质其实是各种数论模板合集

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MOD = 999911659;
const int N = 1E5+10;
typedef long long LL;
LL scan(){LL i=0;cin>>i;return i;}
LL n,m;
LL num[2][N],list[2][N],ans;
LL Mod[N],data[N];
void get(LL nn,LL p[],LL num[]){
p[0]=0;
for(int i=2;(LL)i*i<=nn;i++)
if(nn % i==0){
p[++p[0]] = i;
num[p[0]]=0;
while(nn%i==0)nn/=i,num[p[0]]++;
}
if(nn>1){p[++p[0]] = nn;num[p[0]] = 1;}
}
LL pow(LL x,LL k,LL mod = MOD){
LL re=1;
for(;k;k/=2,x=((LL)x*x)%mod)
if(k&1)re=((LL)re*x)%mod;
return re;
}
void exgcd(LL a,LL b,LL &d,LL &x,LL &y){
if(!a){d=b;x=0;y=1;}
else{exgcd(b%a,a,d,y,x);x-=y*(b/a);}
}
LL lin[N];
void dfs(LL a[],LL b[],int x=1,LL now=1){
int i,j;LL tmp=1;
if(x > a[0]){
lin[++lin[0]] = now;
return;
}
for(i=0;i<=b[x];i++){
dfs(a,b,x+1,now*tmp);
tmp*=a[x];
}
}
LL C(LL a,LL b,LL mod){
if(a < b)return 0;
b = min(b,a-b);
LL up=1,down=1;
for(LL i=0;i<b;i++){
up=up*(a-i)%mod;
down=down*(i+1)%mod;
}return up*pow(down,mod-2,mod)%mod;
}
LL lucas(LL a,LL b,LL P){return b?C(a%P,b%P,P)*lucas(a/P,b/P,P):1;}
LL China(int nn,LL a[],LL m[]){
LL M=1,x,y,d,re=0;
for(int i=1;i<=nn;i++)M*=m[i];
for(int i=1;i<=nn;i++){
LL w =M/m[i];
exgcd(w,m[i],d,x,y);
re = (re+x*w*a[i])%M;
}return (re+M)%M;
}
int main(){
int i,j;
n = scan();m = scan();

//特判!
if(m == MOD){printf("0\n");return 0;}
//中国剩余定理用
get(MOD-1,list[0],num[0]);
//枚举约数
get(n,list[1],num[1]);
dfs(list[1],num[1]);
for(i=1;i<=list[0][0];i++){
Mod[i] = pow(list[0][i],num[0][i]);
for(j=1;j<=lin[0];j++)
data[i] = (data[i]+lucas(n,lin[j],Mod[i])+Mod[i])%Mod[i];
}
//合并
ans = China(list[0][0],data,Mod);
printf("%d",(int)pow(m,ans));
return 0;
}

题解:
费马小定理(欧拉定理)+卢卡斯定理+中国剩余定理
首先发现组合数是指数……好蛋疼
我们由费马小定理得a(p-1) ≡1(mod p)
所以可以把指数部分拆成x + y*(p-1)的形式,那么只要知道x就行了
换句话说就是指数部分模p-1就行了
注意到p是个质数,明显此时p-1就不是质数了,而卢卡斯定理使用的条件是模数必须为质数
因为p-1 = Σpiai
而p-1的所有ai都为1
所以可以拆开之后分别做卢卡斯定理并且用中国剩余定理合并
注意:
1.要尽量用long long,一开始不知道哪里爆int了wa了一片
2.费马小定理/欧拉定理成立的条件是gcd(a,p)=1,当a=p时不成立,会因为这个挂一个点……但是这时很明显答案=0,特判一下就好

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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