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

GreenCloudS

 
 
 

日志

 
 

1876: [SDOI2009]SuperGCD(高精度+更相减损法求GCD)  

2014-06-01 20:51:00|  分类: oi,bzoj,更相减损 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


高精度的话辗转相除明显不靠谱,那么就用更相减损法来求最大公约数即可,然后练手一下高精度即可。


代码(压了9位的高精,跑得蛮快的):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  • #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

  • #define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

  •  

  • const int maxn = 1310 , maxb = 9 ;

  •  

  • int p[ maxb + 1 ] ;

  •  

  • inline void INIT(  ) {

  •     p[ 0 ] = 1 ; rep( i , maxb ) p[ i ] = p[ i - 1 ] * 10 ;

  • }

  •  

  • char s[ maxn * maxb ] ;

  •  

  • struct bignum {

  •      

  •     int a[ maxn ] , n ;

  •      

  •     bignum(  ) {

  •         memset( a , 0 , sizeof( a ) ) ;

  •     }

  •      

  •     inline void read(  ) {

  •         scanf( "%s" , s + 1 ) ;

  •         int len = strlen( s + 1 ) , val ;

  •         if ( len == 1 && s[ 1 ] == '0' ) a[ n = 1 ] = 0 ; else n = 0 ;

  •         for ( int i = len ; i > 0 ; i -= maxb ) {

  •             val = 0 ;

  •             if ( i >= maxb ) REP( j , ( i - maxb + 1 ) , i ) val = val * 10 + s[ j ] - '0'

  •             ; else rep( j , i ) val = val * 10 + s[ j ] - '0' ;

  •             a[ ++ n ] = val ;

  •         }

  •     }

  •      

  •     inline void write(  ) {

  •         printf( "%d" , a[ n ] ) ;

  •         DOWN( i , ( n - 1 ) , 1 ) {

  •             REP( j , 1 , ( maxb - 1 ) ) if ( a[ i ] <= p[ j ] ) printf( "0" ) ;

  •             printf( "%d" , a[ i ] ) ;

  •         }

  •         printf( "\n" ) ;

  •     }

  •      

  •     inline int cmp( const bignum &x ) {

  •         if ( n > x.n ) return 1 ; else if ( n < x.n ) return - 1 ;

  •         DOWN( i , n , 1 ) {

  •             if ( a[ i ] > x.a[ i ] ) return 1 ; else if ( a[ i ] < x.a[ i ] ) return - 1 ;

  •         }

  •         return 0 ;

  •     }

  •      

  •     inline void div2(  ) {

  •         DOWN( i , n , 1 ) {

  •             a[ i - 1 ] += ( a[ i ] & 1 ) * p[ maxb ] ; a[ i ] >>= 1 ;

  •         }

  •         if ( n > 1 && ! a[ n ] ) -- n ;

  •     }

  •      

  •     inline void mul2(  ) {

  •         rep( i , n ) a[ i ] <<= 1 ;

  •         rep( i , n ) if ( a[ i ] >= p[ maxb ] ) {

  •             a[ i + 1 ] += a[ i ] / p[ maxb ] ; a[ i ] %= p[ maxb ] ;

  •         }

  •         n += ( a[ n + 1 ] > 0 ) ;

  •     }

  •      

  •     inline void dec( const bignum &x ) {

  •         rep( i , n ) {

  •             for ( ; a[ i ] < x.a[ i ] ; a[ i ] += p[ maxb ] , -- a[ i + 1 ] ) ;

  •             a[ i ] -= x.a[ i ] ;

  •         }

  •         DOWN( i , n , 1 ) if ( a[ i ] ) {

  •             n = i ; break ;

  •         }

  •     }

  •      

  •     inline bool odd(  ) {

  •         return a[ 1 ] & 1 ;

  •     }

  •      

  •     inline bool check(  ) {

  •         return a[ 1 ] == 0 && n == 1 ;

  •     }

  •      

  • } n1 , n2 , ans , temp ;

  •  

  • int cnt = 0 ;

  •  

  • int main(  ) {

  •     INIT(  ) ; n1.read(  ) ; n2.read(  ) ;

  •     if ( n1.check(  ) ) {

  •         n2.write(  ) ; return 0 ;

  •     }

  •     if ( n2.check(  ) ) {

  •         n1.write(  ) ; return 0 ;

  •     }

  •     for ( int rec = n1.cmp( n2 ) ; rec ; rec = n1.cmp( n2 ) ) {

  •         if ( n1.odd(  ) ) {

  •             if ( n2.odd(  ) ) {

  •                 if ( rec == 1 ) n1.dec( n2 ) ; else n2.dec( n1 ) ;

  •             } else n2.div2(  ) ;

  •         } else {

  •             if ( n2.odd(  ) ) n1.div2(  ) ; else ++ cnt , n1.div2(  ) , n2.div2(  ) ;

  •         }

  •     }

  •     ans = n1 ;

  •     while ( cnt -- ) ans.mul2(  ) ;

  •     ans.write(  ) ;

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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