首页 > 代码库 > Description has only two Sentences(hdu3307)
Description has only two Sentences(hdu3307)
Description has only two Sentences
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1108 Accepted Submission(s): 345
Problem Description
an = X*an-1 + Y and Y mod (X-1) = 0.
Your task is to calculate the smallest positive integer k that ak mod a0 = 0.
Your task is to calculate the smallest positive integer k that ak mod a0 = 0.
Input
Each line will contain only three integers X, Y, a0 ( 1 < X < 231, 0 <= Y < 263, 0 < a0 < 231).
Output
For each case, output the answer in one line, if there is no such k, output "Impossible!".
Sample Input
2 0 9
Sample Output
1
Author
WhereIsHeroFrom
思路：baby_step；
先构造等比数列，a[n]=X*a[n-1]+Y;那么（a[n]+k）=X（a[n-1]+k）;那么展开求得k=（Y）/（X-1）；那么a[n]+k=（a[0]+k）*(x)^n;
然后a[n]=(a[0]+k)*(x)^n-k;那么要求最小的n满足a[n]%a[0]=0;那么就是求k*x^n%(a[0]) = k%a[0],那么这个用扩展baby_step；求下就可以了，复杂度（sqrt（a[0]）*log(a[0])）;
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<set> 7 #include<math.h> 8 #include<map> 9 using namespace std; 10 typedef long long LL; 11 typedef struct node 12 { 13 LL x; 14 LL id; 15 } ss; 16 ss ans[600000]; 17 ss bns[600000]; 18 pair<LL,LL>exgcd(LL n,LL m); 19 LL gcd(LL n,LL m); 20 LL quick(LL n,LL m,LL mod); 21 bool cmp(node p,node q) 22 { 23 if(p.x==q.x) 24 return p.id<q.id; 25 else return p.x<q.x; 26 } 27 LL er(int n,int m,LL k); 28 int main(void) 29 { 30 LL x,y,a; 31 while(scanf("%lld %lld %lld",&x,&y,&a)!=EOF) 32 { 33 int kp = 0; 34 LL t = y/(x-1);//printf("%lld\n",t); 35 LL tt = t%a; 36 if(t%a==0) 37 { 38 printf("1\n"); 39 } 40 else 41 { 42 t%=a; 43 int flag = 0; 44 LL cnt = 0; 45 LL as = 1; 46 while(true) 47 { 48 LL gc = gcd(x,a); 49 if(gc == 1) 50 break; 51 else if(t%gc==0) 52 { 53 cnt++; 54 a/=gc; 55 as*=x/gc; 56 t/=gc; 57 as%=a; 58 } 59 else if(t%gc) 60 { 61 kp = 1; 62 break; 63 } 64 if(t*as%gc==t) 65 { 66 flag = 1; 67 break; 68 } 69 } 70 if(kp)printf("Impossible!\n"); 71 else if(flag) 72 printf("%lld\n",cnt+1); 73 else 74 { 75 LL v = sqrt(1.0*a); 76 pair<LL,LL>acc = exgcd(x,a); 77 LL xx = quick(x,v,a); 78 int i;//printf("%lld\n",xx); 79 acc.first = (acc.first%a+a)%a; 80 LL sum = t*acc.first%a; 81 int cn = 0; 82 for(i = 1; i <= v; i++) 83 { 84 ans[cn].x= sum%a; 85 ans[cn].id = i; 86 cn++; 87 sum = sum*acc.first%a; 88 } 89 sort(ans,ans+cn,cmp); 90 91 bns[0]=ans[0]; 92 LL cc = ans[0].x; 93 int ac = 1; 94 for(i = 1; i < cn; i++) 95 { 96 if(ans[i].x!=cc) 97 { 98 cc = ans[i].x; 99 bns[ac].x = ans[i].x;100 bns[ac].id = ans[i].id;101 ac++;102 }103 }104 LL akk = as*tt%a;105 LL idd;//printf("%lld\n",bns[2].x);106 for(i = 0; i <= v; i++)107 {108 idd = er(0,ac-1,akk);109 if(idd!=-1)110 break;111 akk = akk*xx%a;112 }113 if(i==v+1)114 {115 printf("Impossible!\n");116 }117 else118 {119 printf("%lld\n",cnt+i*v+idd);120 }121 }122 }123 }124 return 0;125 }126 pair<LL,LL>exgcd(LL n,LL m)127 {128 if(m==0)129 return make_pair(1,0);130 else131 {132 pair<LL,LL>ak = exgcd(m,n%m);133 return make_pair(ak.second,ak.first-(n/m)*ak.second);134 }135 }136 LL gcd(LL n,LL m)137 {138 if(m==0)139 return n;140 else return gcd(m,n%m);141 }142 LL quick(LL n,LL m,LL mod)143 {144 LL ak = 1;145 n %= mod;146 while(m)147 {148 if(m&1)149 ak =ak*n%mod;150 n = n*n%mod;151 m>>=1;152 }153 return ak;154 }155 LL er(int n,int m,LL k)156 {157 int mid = (n+m)/2;158 if(n>m)return -1;159 if(bns[mid].x == k)160 {161 return bns[mid].id;162 }163 else if(bns[mid].x < k)164 {165 return er(mid+1,m,k);166 }167 else return er(n,mid-1,k);168 }
Description has only two Sentences(hdu3307)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。