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.

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

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
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
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 pairexgcd(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.idacc = 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 else 118 { 119 printf("%lld\n",cnt+i*v+idd); 120 } 121 } 122 } 123 } 124 return 0; 125 } 126 pairexgcd(LL n,LL m)
127 {
128 if(m==0)
129 return make_pair(1,0);
130 else
131 {
132 pairak = 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 }

baby_step

手机扫一扫

移动阅读更方便

你可能感兴趣的文章