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

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

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

 
 
 

日志

 
 

zoj 3254  

2010-10-17 17:53:27|  分类: zoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
给定 A、D、 P、 M, 求A^x == D (mod P) ,这样的x,满足0<=x<=M的个数。 (1 <= AP < 2^31, 0 <= D < P, 1 <= M < 2^63)
题目数据比较大,有些难度。
首先我们可以求出最小的x0,这个可以根据baby-step gaint-step来求出来,然后就是求循环节,注意到循环节肯定是p的欧拉函数的约数,于是可以试除素因数,来找到最小的循环节x,然后答案就是(M-x0)/x+1
然后就是注意一个小trick,注意到数据范围M < 2^63,这样答案可能会达到2^63,所以最后的答案要用unsigned long long存储(膜拜Aekdycoin核武的提示)
#include<cstdio>
#include<cstring>
#include<map>
#include<iterator>
#include<iostream>
#include<cmath>
using namespace std;
const long long mm=1<<20;
long long k,p,n,ans,h1[mm],h2[mm];
long long r;
long long gcd(long long a,long long b){
if(b==0)
return a;
return gcd(b,a%b);
}
long long mod(long long a,long long x,long long m){
long long ret=1%m;
while(x){
if(x&1)
ret=(long long)ret*a%m;
a=(long long)a*a%m;
x>>=1;
}
return ret;
}
long long egcd(long long a,long long b,long long &x,long long &y){
if(b==0){
x=1;
y=0;
return a;
}
long long tmp=egcd(b,a%b,y,x);
y-=(a/b)*x;
return tmp;
}
long long ivt(long long a,long long m){
long long x,y;
egcd(a,m,x,y);
return (x%m+m)%m;
}
void in(long long x,long long y){
long long z=x&(mm-1);
while(h1[z]!=-1&&h1[z]!=x)
z=(z+1)&(mm-1);
h1[z]=x;
h2[z]=y;
}
long long find(long long x){
long long z=x&(mm-1);
while(h1[z]!=-1&&h1[z]!=x)
z=(z+1)&(mm-1);
if(h1[z]==-1)
return -1;
return h2[z];
}
long long solve(){
if(n==1||(n==0&&p==1))
return 0;
long long x=1;
for(long long i=1;i<60;++i){
x=(long long)x*k%p;
if(x==n)
return i;
}
long long d,kk=1%p,kk0=0;
while((d=gcd(k,p))!=1){
if(n%d)
return -1;
kk0++;
p/=d;
n/=d;
kk=(long long)k/d*kk%p;
}
long long a=sqrt(p)+1;
long long aa=n;
long long tmp=ivt(k,p);
map<long long,long long>h;
for(long long i=0;i<=a;++i){
if(h.find(aa)!=h.end())
break;
h[aa]=i+1;
aa=(long long)aa*tmp%p;
}
tmp=mod(k,a,p);
aa=kk;
for(long long i=0;i<=a;++i){
if(h.find(aa)!=h.end())
return i*a+h[aa]+kk0-1;
aa=(long long)aa*tmp%p;
}
return -1;
}
long long euler(long long n){
    long long m=1;
    for(long long i=2;(long long)i*i<=n;i++)
      if(!(n%i)){
        n/=i;
        m*=(i-1);
        while(!(n%i)){
          m*=i;
          n/=i;
        }     
      }
    if(n!=1)
      m*=(n-1);
    return m;
}
int main(){
while(scanf("%lld%lld%lld",&k,&p,&n)!=EOF){
n%=p;
k%=p;
long long k1=k,p1=p,n1=n;
scanf("%lld",&r);
if((ans=solve())==-1||r-ans<0){
printf("0\n");
continue ;
}
long long x=euler(p1);
if(mod(k1,(long long)ans+x,p1)!=n1){
printf("1\n");
continue ;
}
long long x1=x;
for(long long i=2;x1>1;i=(long long)i*i<=x1?i+1:x1)
if(x1%i==0){
while(x1%i==0)
x1/=i;
while(x%i==0&&mod(k1,(long long)ans+x/i,p1)==n1)
x/=i;
}
unsigned long long ret=(unsigned long long)(r-ans)/x+1;
cout<<ret<<endl;
}
return 0;
}

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

历史上的今天

评论

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

页脚

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