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

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

POJ 1808  

2010-05-28 12:34:22|  分类: poj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Legendre符号就是用来表示(d/p)d是否是p的二次剩余,通过Legendre符号的性质,以及Gaus二次互反律可以推出结果
#include<cstdio>
int t,p,a,k=0;
int check(int x){
if(x%2)
return -1;
return 1;
}
int solve(int k1,int k2){
if(k1==1)
return 1;
if(k1==2)
return check((k2*k2-1)/8);
int ans=1;
while(k1%2==0){
k1/=2;
ans*=check((k2*k2-1)/8);
}
for(int i=3;k1>1;i=i*i<=k1?i+1:k1)
if(k1%i==0){
while(k1%i==0){
ans*=check((i-1)*(k2-1)/4)*solve(k2%i,i);
k1/=i;
}
}
return ans;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&a,&p);
printf("Scenario #%d:\n%d\n\n",++k,solve((a%p+p)%p,p));
}
}
  评论这张
 
阅读(498)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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