http://acm.hdu.edu.cn/showproblem.php?pid=5447

 

网上好像只找到java的题解，写完就发一下c++代码咯，顺便纪念一下+存个int128板子

做法可以看tjz直播中的pdf：http://www.51nod.com/live/liveDescription.html#!liveId=5

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ll MMH#define ull unsigned long longusing namespace std;inline ull M(ull x,ull MOD){ while (x>=MOD)x-=MOD;return x;}inline ull cheng(ull a,ull b,ull p){ ull mmh=0; while (b){ if (b&1) mmh=M(mmh+a,p); a=M(a+a,p);b>>=1; } return mmh;}char P_C[50],O_O[50];char c[50]={ "24408308522758834075998738377"};char ss[36][50]={ "18446744073709551616","36893488147419103232","73786976294838206464","147573952589676412928","295147905179352825856","590295810358705651712","1180591620717411303424","2361183241434822606848","4722366482869645213696","9444732965739290427392","18889465931478580854784","37778931862957161709568","75557863725914323419136","151115727451828646838272","302231454903657293676544","604462909807314587353088","1208925819614629174706176","2417851639229258349412352","4835703278458516698824704","9671406556917033397649408","19342813113834066795298816","38685626227668133590597632","77371252455336267181195264","154742504910672534362390528","309485009821345068724781056","618970019642690137449562112","1237940039285380274899124224","2475880078570760549798248448","4951760157141521099596496896","9903520314283042199192993792","19807040628566084398385987584","39614081257132168796771975168","79228162514264337593543950336","158456325028528675187087900672","316912650057057350374175801344","633825300114114700748351602688"};inline bool ju(int i){ int cl=strlen(c),sl=strlen(ss[i]); if (cl
            
             ss[i][j]) break; for (register int j=0;j
             
              cl) cl=sl; for (i=0;i
              
               =10) O_O[i+1]+=O_O[i]/10,O_O[i]%=10,cl+=i==(cl-1); for (i=0;i
               
                >=1; if (a&1) b|=1ull<<63; a>>=1; } void two(){ a<<=1; if (b&(1ull<<63)) a|=1; b<<=1; } void pr(){ ull A=a,B=b;int s=0; memset(P_C,0,sizeof(P_C)); memset(O_O,0,sizeof(O_O)); while(B) O_O[s++]=B%10+48,B/=10;P_C[s]=0; for (register int i=0;i
                
                 x.b) z.a--; return z;}MMH operator -(const MMH &x,const int &y){ MMH z=x; if (z.b
                 
                  >32)*(y.b>>32),_b1=(x.b&s)*(y.b>>32),b=_b1+(x.b>>32)*(y.b&s),c=(x.b&s)*(y.b&s),d; a+=(b<_b1)*1ull<<32; d=c+((b&s)<<32);a+=d
                  
                   >32; return MMH(a,d);}bool operator <(const MMH &x,const MMH &y){ return x.a==y.a?x.b
                   
                    
                     (const MMH &x,const MMH &y){ return x.a==y.a?x.b>y.b:x.a>y.a;}bool operator !=(const MMH &x,const MMH &y){ return x.a!=y.a||x.b!=y.b;}bool operator ==(const MMH &x,const MMH &y){ return x.a==y.a&&x.b==y.b;}MMH operator %(const MMH &x,const MMH &y){ if (x
                     
                      c)) z.two(); for(;;){ z.half(); if (!(c
                      
                       x)) z.two(); for(;;){ z.half();a.two(); if (!(c
                       
                        =y) z.b-=y; return z.b;}ull sqrt(MMH x){ ull l=0,r=1e18,_mid; MMH mid; while (l
                        
                         >1; mid=mid*mid; if (x==mid) return _mid;else if (x
                         
                          mid) l=_mid+1; } return l;}ull sqrt3(MMH x){ ull l=0,r=1e12,_mid; MMH mid=MMH(0,0); while (l
                          
                           >1; mid=mid*mid*mid; if (x==mid) return _mid;else if (x
                           
                            mid) l=_mid+1; } return l;}ull operator %(const MMH &x,const ull &y){ MMH z=x; z.a%=y;z.b%=y; for (int i=0;i<64;i++) z.a<<=1,z.a%=y; z.b+=z.a;if (z.b>=y) z.b-=y; return z.b;}inline void read(MMH &n){ scanf("%s",c); n.a=n.b=0; for (int i=35;i>=0;i--){ n.a<<=1; if (ju(i)) n.a|=1; } n.b=change();}const int S=20;const ull m_p[20]={ 2,5,7,61,97,37,101,13,11,997,2083,5807,7213,9907,10781,11897,14033,18013,43789,10009};ll cheng(ll a,ll b,ll p){ ll mmh;mmh=MMH{ 0,0}; while (b.a||b.b){ if (b.b&1) if (mmh=mmh+a,!(mmh