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. InputThe input consists of several test cases.Every cases have only three integers indicating K, P, N. (1<=K, P, N<=10^9) OutputThe minimize D.If you can’t find such D, just output “Orz,I can’t find D!” Sample Input3 78992 4534 1314520 655365 1234 67 Sample OutputOrz,I can’t find D!820 AuthorAekdyCoin SourceHDU 1st “Old-Vegetable-Birds Cup” Programming Open Contest Recommendlcy | We have carefully selected several similar problems for you: 2814 2809 2447 2810 2811題解：擴展BSGS
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<map>#define LL long long using namespace std;LL a,p,b;map<LL,LL> mp;LL quickpow(LL num,LL x){ LL base=num%p; LL ans=1; while (x) { if (x&1) ans=ans*base%p; x>>=1; base=base*base%p; } return ans;}LL gcd(LL x,LL y){ LL r; while (y) { r=x%y; x=y; y=r; } return x;}LL exbsgs(LL a,LL b,LL p){ a%=p; b%=p; if (b==1) return 0; LL cnt=0,d=1,tmp=1; while ((tmp=gcd(a,p))!=1) { if (b%tmp) return -1; b/=tmp; p/=tmp; cnt++; d=d*(a/tmp)%p; if (b==d) return cnt; } LL m=ceil(sqrt(p)); LL ans=b; LL sum=1; mp.clear(); tmp=quickpow(a,m); mp[ans]=0; for (LL i=1;i<=m;i++) ans=ans*a%p,mp[ans]=i; for (int LL i=1;i<=m+1;i++) { d=d*tmp%p; if (mp[d]) { return i*m-mp[d]+cnt; } } return -1;}int main(){ freopen("a.in","r",stdin); while (scanf("%I64d%I64d%I64d",&a,&p,&b)!=EOF) { if (b>=p) { printf("Orz,I can’t find D!/n"); continue; } LL t=exbsgs(a,b,p); if (t!=-1) printf("%I64d/n",t); else printf("Orz,I can’t find D!/n"); }}
新聞熱點
疑難解答
