首页 > 代码库 > HDU 2815 Mod Tree (扩展 Baby Step Giant Step )
HDU 2815 Mod Tree (扩展 Baby Step Giant Step )
Mod Tree |
| Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
| Total Submission(s): 96 Accepted Submission(s): 38 |
Problem Description  The picture indicates a tree, every node has 2 children. The depth of the nodes whose color is blue is 3; the depth of the node whose color is pink is 0. Now out problem is so easy, give you a tree that every nodes have K children, you are expected to calculate the minimize depth D so that the number of nodes whose depth is D equals to N after mod P. |
Input The input consists of several test cases. Every cases have only three integers indicating K, P, N. (1<=K, P, N<=10^9) |
Output The minimize D. If you can’t find such D, just output “Orz,I can’t find D!” |
Sample Input 3 78992 4534 1314520 655365 1234 67 |
Sample Output Orz,I can’t find D!820 |
Author AekdyCoin |
证明来自：
http://hi.baidu.com/aekdycoin/item/236937318413c680c2cf29d4
#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long LL ;const int N = 100010;struct B{ LL num , id ; bool operator < ( const B &a ) const{ if( num != a.num ) return num < a.num; else return id < a.id ; }}baby[N];LL n , k , p ;int tot ;void e_gcd( LL &x , LL &y , LL &d , LL a , LL b ){ if( b == 0 ){ x = 1 , y = 0 ; d = a ; return ; } e_gcd( y , x , d , b , a%b ); y -= x* (a/b) ;}int inv( LL a, LL b ,LL n ){ LL d,e,x,y ; e_gcd(x,y,d,a,n); e = ( x * b ) % n ; return e < 0 ? e + n : e;}inline LL gcd(LL a, LL b ){ return b == 0 ? a : gcd( b , a % b ) ; }LL quick_mod( LL a , LL b ,LL mod ){ LL res =1 ; while( b ) { if( b &1 ) res = res * a % mod ; a = a * a % mod ; b >>= 1 ; } return res ;}int find( LL n ){ int l = 0 , r = tot - 1 ; while( l <= r ){ int m = (l + r) >> 1; if( baby[m].num == n){ return baby[m].id; } else if( baby[m].num < n ) l = m + 1; else r = m - 1 ; } return -1;}void run(){ if( p <= n ){ puts("Orz,I can’t find D!"); return ; } LL temp = 1 % p ; for( int i = 0 ; i < 100 ; ++i ) { if( temp == n ){ printf("%d\n",i); return ; } temp = temp * k % p ; } LL d = 0 , kk = 1 % p ; while( ( temp = gcd( k , p ) ) != 1 ){ if( n % temp ) { puts("Orz,I can’t find D!"); return ; } d ++ ; p /= temp; n /= temp; kk = k / temp * kk % p ; } int m = ( int ) ceil( sqrt( (double)p ) ); baby[0].num = 1 , baby[0].id = 0 ; for( int i = 1 ; i <= m ; ++i ){ baby[i].num = baby[i-1].num * k % p ; baby[i].id = i ; } sort( baby , baby + m + 1 ) ; tot = 1 ; for( int i = 1 ; i <= m ; ++i ){ if(baby[i].num != baby[tot-1].num ){ baby[tot++] = baby[i]; } } LL am = quick_mod( k , m , p ); for( int j = 0 ; j <= m ; ++j ){ temp = inv(kk,n,p); if( temp < 0 ){ continue ; } int pos = find( temp ); if( pos != -1 ){ printf("%d\n", m * j + d + pos ); return ; } kk = kk * am % p ; } puts("Orz,I can’t find D!");}int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL while( scanf("%I64d%I64d%I64d",&k,&p,&n) != EOF ) run();}
HDU 2815 Mod Tree (扩展 Baby Step Giant Step )
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。