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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2242: [SDOI2011]计算器(快速幂+拓展欧几里德+Baby Step Giant Step)  

2014-07-03 17:18:00|  分类: oi,bzoj,数论,快 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2242


第一个操作,直接快速幂即可

第二个操作,拆了之后拓展欧几里德,然后调调看有没有合适的解

第三个操作,Baby Step Giant Step算法,事实上就是分块思想?:

令L=int(sqrt(P)),x=kL+i

则y^(kL+i)=Z(mod P),那么假如y存在关于P的乘法逆元,则y^i=Z*(y^(kL))^(-1)(mod P),那么先预处理出y^i,全部塞到一个数据结构里边去(HASH或SET即可),然后枚举k,就可以找到x了。

注意:上面是假设y存在逆元,如果y不存在逆元,即y是P的倍数,那么y^x=0(mod P)对任意x成立,所以应该直接输出无解。


代码:

  • #include <cstdio>

  • #include <cstring>

  • #include <algorithm>

  • #include <cmath>

  • #include <set>

  •  

  • using namespace std ;

  •  

  • typedef long long ll ;

  •  

  • ll Y , Z , P ;

  •  

  • inline ll power( ll x , ll cnt ) {

  •         ll y = 1 ;

  •         for ( ; cnt ; cnt >>= 1 ) {

  •                 if ( cnt & 1 ) y = ( ll ) y * x % P ;

  •                 x = ( ll ) x * x % P ;

  •         }

  •         return y ;

  • }

  •  

  • inline void swap( ll &x , ll &y ) {

  •         ll z = x ; x = y ; y = z ;

  • }

  •  

  • inline ll gcd( ll x , ll y ) {

  •         if ( x < y ) swap( x , y ) ;

  •         for ( ll k ; y ; k = y , y = x % y , x = k ) ;

  •         return x ;

  • }

  •  

  • struct par {

  •         ll first , second ;

  •         par( ll _first , ll _second ) : first( _first ) , second( _second ) {

  •         }

  • } ;

  •  

  • par exgcd( ll a , ll b ) {

  •         if ( ! b ) return par( 1 , 0 ) ;

  •         par temp = exgcd( b , a % b ) ;

  •         return par( temp.second , temp.first - ( a / b ) * temp.second ) ;

  • }

  •  

  • inline void solve2(  ) {

  •         ll g = gcd( Y , P ) ;

  •         if ( Z % g ) {

  •                 printf( "Orz, I cannot find x!\n" ) ; return ;

  •         }

  •         par res( 0 , 0 ) ;

  •         if ( Y > P ) res = exgcd( Y / g , P / g ) ; else {

  •                 res = exgcd( P / g , Y / g ) ; swap( res.first , res.second ) ;

  •         }

  •         if ( res.first > 0 ) {

  •                 ll ret = res.first / ( P / g ) ;

  •                 res.first -= ret * ( P / g ) , res.second += ret * ( Y / g ) ;

  •         }

  •         if ( res.first < 0 ) {

  •                 ll ret = ( - res.first ) / ( P / g ) + ( ( ( - res.first ) % ( P / g ) ) > 0 ) ;

  •                 res.first += ret * ( P / g ) , res.second -= ret * ( Y / g ) ;

  •         }

  •         if ( res.second > 0 ) {

  •                 ll ret = res.second / ( Y / g ) + ( ( res.second % ( Y / g ) ) > 0 ) ;

  •                 res.first += ret * ( P / g ) , res.second -= ret * ( Y / g ) ;

  •         }

  •         printf( "%lld\n" , res.first * ( Z / g ) % P ) ;

  • }

  •  

  • struct point {

  •         ll v , t ;

  •         point( ll _v , ll _t ) : v( _v ) , t( _t ) {

  •         }

  •         bool operator < ( const point &x ) const {

  •                 return v < x.v ;

  •         }

  •         bool operator == ( const point &x ) const {

  •                 return v == x.v ;

  •         }

  • } ;

  • set < point > bst ;

  •  

  • inline void solve3(  ) {

  •         if ( gcd( Y , P ) > 1 ) {

  •                 printf( "Orz, I cannot find x!\n" ) ; return ;

  •         }

  •         ll L = ll( sqrt( P ) ) ;

  •         bst.clear(  ) ;

  •         for ( ll i = 0 , j = 1 ; i < L ; ++ i , j = ( ll ) j * Y % P ) {

  •                 if ( bst.find( point( j , i ) ) == bst.end(  ) ) bst.insert( point( j , i ) ) ;

  •         }

  •         for ( ll i = 0 , j = P / L ; i <= j ; ++ i ) {

  •                 ll val = ( ll ) Z * power( power( Y , i * L ) , P - 2 ) % P ;

  •                 set < point > :: iterator p = bst.find( point( val , 0 ) ) ;

  •                 if ( p != bst.end(  ) ) {

  •                         printf( "%lld\n" , i * L + p -> t ) ; return ;

  •                 }

  •         }

  •         printf( "Orz, I cannot find x!\n" ) ;

  • }

  •  

  • ll T , K ;

  •  

  • int main(  ) {

  •         scanf( "%lld%lld" , &T , &K ) ;

  •         while ( T -- ) {

  •                 scanf( "%lld%lld%lld" , &Y , &Z , &P ) ;

  •                 if ( K == 1 ) printf( "%lld\n" , power( Y , Z ) ) ; else

  •                 if ( K == 2 ) solve2(  ) ; else solve3(  ) ;

  •         }

  •         return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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