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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

Unis Cup 1.0 Infinity 素数测试和质因数分解算法  

2013-04-07 10:48:28|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
好吧,其实是个结论a^x=a^(x%phi(p)+phi(p)) mod p,当x>phi(p)时

当作模板题放在这儿吧。。由于讲课的原因落下了好多好多东西,郁闷得要死
质因数分解的那个算法记得很久很久看算导时就看了。。。然后像我看算导的通常节奏,看完就忘了了。而且我对于这种蛋疼的概率算法一直没有兴趣。。不过还是很好的。
此题的算法其实挺纠结的。。我用的是结论——喜闻乐见地套结论,不管证明~

代码如下,依旧不知道质因数分解的那个概率算法的名字是什么
感谢长郡神犇团带来的神题

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int MAX=200+10;
const LL INF=1LL<<61;

LL n,p;
LL a[MAX];
LL b[MAX];

struct Int
{
LL a,p;
Int():a(0),p(1000000007){}
Int(const Int& b):a(b.a),p(b.p){}
Int(LL x,LL y):a(x),p(y){}
};

Int operator + (Int a,Int b)
{
return Int( (a.a+b.a+a.p)%a.p,a.p );
}

Int operator - (Int a,Int b)
{
return Int( (a.a-b.a+a.p)%a.p,a.p );
}

Int operator * (Int a,Int b)
{
Int ans(0LL,a.p);
LL c=b.a;
for(;c;c=c/2,a=a+a)
if(c%2==1)
ans=ans+a;
return ans;
}

Int operator ^ (Int a,LL b)//快速幂运算
{
Int ans(1,a.p);
for(;b;b=b/2,a=a*a)
if(b%2==1)
ans=ans*a;
return ans;
}

int Miller_Rabin(LL a)//检验a是否是质数
{
if(a==2 || a==3)return 1;
if(a==1 || a%2==0 || a%3==0)
return 0;
int t=10;
while(t--)
{
LL p=(LL)rand()*rand()%(a-2)+2;
LL d=a-1;
for(;d%2==0;d/=2);
Int tmp= ( Int(p,a)^d );
if(tmp.a==1 || tmp.a==a-1)
continue;
for(;d!=a-1 && tmp.a!=1 && tmp.a!=a-1;d*=2)
tmp=tmp*tmp;
if(tmp.a==a-1)
continue;
return 0;
}
return 1;
}

LL gcd(LL a,LL b)//欧几里得算法^_^
{
return b?gcd(b,a%b):a;
}

LL pho(LL n)//似乎是想得质因数分解——完全不靠谱的样子
{
int d=1;
while(1)
{
Int x=Int( (LL)rand()*rand()%n,n );
Int y=x;
LL k=2;
int i=1;
while(1)
{
++i;
x=x*x+Int(d,n);
Int dif=y-x;
if(!dif.a)
break;
LL g=gcd(dif.a,n);
if(n%g==0 && g!=1 && g!=n)
return g;
if(i==k)
{
y=x;
k*=2;
}
}
d++;
}
}

LL phi(LL a)//求个尼玛的欧拉函数
{
if(a==1)
return 0;
if(Miller_Rabin(a))
return a-1;
else
{
LL d=pho(a);
while(!Miller_Rabin(d))
d=pho(d);
LL ans=d-1;
a/=d;
for(;a%d==0;a/=d,ans*=d);
if(a==1)
return ans;
return ans*phi(a);
}
}

LL calc(int i,LL p)
{
if(i==n+1)return 1;
if(b[i]!=-1)return b[i];
LL ans;
if(p!=1)
{
ans=phi(p);
LL k=calc(i+1,ans)%ans;
ans+=k;
}
else ans=0;
return (Int(a[i],p)^ans).a;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i;
cin>>n>>p;
REP(i,1,n)
cin>>a[i];
memset(b,-1,sizeof b);
b[n+1]=1;
for(i=n;i>=1;--i)
{
ld tmp=pow((ld)a[i],b[i+1]);
if(tmp>INF)
break;
b[i]=( Int(a[i],INF)^b[i+1] ).a;
}
cout<<calc(1,p)%p<<endl;
return 0;
}



  评论这张
 
阅读(415)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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