Mod Tree

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4105 Accepted Submission(s): 1068

Problem Description

The picture indicates a tree, every node has 2 children.
The depth of the nodes whZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc2UgY29sb3IgaXMgYmx1ZSBpcyAzOyB0aGUgZGVwdGggb2YgdGhlIG5vZGUgd2hvc2UgY29sb3IgaXMgcGluayBpcyAwLjxicj4KICBOb3cgb3V0IHByb2JsZW0gaXMgc28gZWFzeSwgZ2l2ZSB5b3UgYSB0cmVlIHRoYXQgZXZlcnkgbm9kZXMgaGF2ZSBLIGNoaWxkcmVuLCB5b3UgYXJlIGV4cGVjdGVkIHRvIGNhbGN1bGF0ZSB0aGUgbWluaW1pemUgZGVwdGggRCBzbyB0aGF0IHRoZSBudW1iZXIgb2Ygbm9kZXMgd2hvc2UgZGVwdGggaXMgRCBlcXVhbHMgdG8gTiBhZnRlciBtb2QgUC4KIAo8YnI+CklucHV0ClRoZSBpbnB1dCBjb25zaXN0cyBvZiBzZXZlcmFsIHRlc3QgY2FzZXMuPGJyPgpFdmVyeSBjYXNlcyBoYXZlIG9ubHkgdGhyZWUgaW50ZWdlcnMgaW5kaWNhdGluZyBLLCBQLCBOLiAoMTw9SywgUCwgTjw9MTBeOSkKIAo8YnI+Ck91dHB1dApUaGUgbWluaW1pemUgRC48YnI+CklmIHlvdSBjYW6hr3QgZmluZCBzdWNoIEQsIGp1c3Qgb3V0cHV0IKGwT3J6LEkgY2Fuoa90IGZpbmQgRCGhsQogCjxicj4KU2FtcGxlIElucHV0Cgo8cHJlIGNsYXNzPQ=="brush:java;">3 78992 453 4 1314520 65536 5 1234 67
Sample Output

Orz,I can’t find D!
8
20

Author AekdyCoin

基本是测试模板。

代码：

/* ***********************************************
Author :rabbit
Created Time :2014/4/2 21:01:29
File Name :7.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; class HASH{ public: struct node{ ll next,first,second; }edge[140000]; ll tol,head[140100]; void clear(){ memset(head,-1,sizeof(head)); tol=0; } void add(ll x,ll y){ if(find(x)!=-1)return; ll t=x%65535; edge[tol].next=head[t]; edge[tol].first=x; edge[tol].second=y; head[t]=tol++; } ll find(ll x){ ll t=x%65535; for(ll i=head[t];i!=-1;i=edge[i].next) if(edge[i].first==x)return edge[i].second; return -1; } }mi; ll gcd(ll a,ll b) { return b==0 a:gcd(b,a%b); } ll ext_gcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1,y=0; return a; } ll d=ext_gcd(b,a%b,y,x); y-=a/b*x; return d; } ll pow_mod(ll a,ll n,ll m) { ll res=1; a%=m; while(n) { if(n&1) res=res*a%m; a=a*a%m; n>>=1; } return res; } ll BabyStep_GiantStep(ll A,ll B,ll C) { B%=C; ll tmp=1;mi.clear(); for(int i=0;i<=100;++i) { if(tmp==B%C) return i; tmp=tmp*A%C; } ll D=1,d=0; while((tmp=gcd(A,C))!=1) { if(B%tmp) return -1; C/=tmp; B/=tmp; D=D*A/tmp%C; d++; } ll m=(ll)ceil(sqrt((double)C)); tmp=1; for(int i=0;i<=m;++i) { mi.add(tmp,i); tmp=tmp*A%C; } ll x,y,K=pow_mod(A,m,C); for(int i=0;i<=m;++i) { ext_gcd(D,C,x,y); tmp=((B*x)%C+C)%C; if((y=mi.find(tmp))!=-1) return i*m+y+d; D=D*K%C; } return -1; } int main() { ll A, B, C; while( scanf("%I64d%I64d%I64d",&A,&C,&B ) !=EOF ) { if(B>C) { printf("Orz,I can’t find D!\n"); continue; } ll tmp = BabyStep_GiantStep ( A, B, C ); if ( tmp == -1 )puts("Orz,I can’t find D!"); else printf("%I64d\n",tmp); } return 0; }

hdu 2815 大步小步

Mod Tree