程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 2815 大步小步

hdu 2815 大步小步

編輯：C++入門知識

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.Bkjia.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;
}