I have n tickets for a train with a rabbit. Each ticket is numbered from 0 to n − 1, and…
- User
I have n tickets for a train with a rabbit. Each ticket is numbered from 0 to n − 1, and you can use the k ticket to go to p⋅ak + q⋅bk station.
Rabbit wants to go to the all-you-can-eat carrot shop at the station m station ahead of the current station, but wants to walk as short as possible. The stations are lined up at regular intervals. When using, how many stations can a rabbit walk to reach the store? Input
1 ≤ n, m, a, b, p, q ≤ 1 000 000 000 000 (integer)
Output
Output the number of rabbits that can reach the store on foot at the minimum number of stations in one line.
Examples
Input
6 200 2 3 4 5
Output
1
Input
6 1 2 3 4 5
Output
1
Assistant
We need to parse problem statement. It appears there is a train with a rabbit? Possibly a combinatorial or number theory problem.
We have n tickets, each numbered k from 0 to n-1. Using ticket k, you can go to p * a^k + q * b^k station? Actually statement: "you can use the k ticket to go to p⋅ak + q⋅bk station." It likely means p * a_k? But it says "p⋅ak + q⋅bk". Could be p * a_k + q * b_k? But a and b are given constants, so likely p * a^k + q * b^k? However they wrote "ak" and "bk", maybe meaning a_k and b_k? But given input includes a,b,p,q. So likely p * a^k + q * b^k? The problem: "Each ticket is numbered from 0 to n − 1, and you can use the k ticket to go to p⋅ak + q⋅bk station." It might be interpreted as: using ticket k, you can go to p * a_k + q * b_k stations, but a and b are given constants, so probably a^k and b^k. The notation "ak" could be a^k. Many problems use exponent. Alternatively could be p * a_k where a_k is something like a sequence? But input a and b are given, so likely pa^k + qb^k. But then there is also m: the carrot shop at station m ahead of current station. The rabbit wants to go to the shop but walk as short as possible. The stations are lined up at regular intervals. When using, how many stations can a rabbit walk to reach the store? Hmm.
Maybe the rabbit is initially at some station, and has n tickets. Each ticket k allows him to travel by some number of stations: i.e., if he uses ticket k, he moves from his current station to the station that is pa^k + qb^k stations ahead (or maybe the absolute station number? It says "go to p⋅ak + q⋅bk station." That phrase ambiguous: could be that he goes directly to station number pa^k + qb^k? But that would be an absolute station number? Then m is the target station ahead of current. Actually: "Rabbit wants to go to the all-you-can-eat carrot shop at the station m station ahead of the current station" Means the shop is located at the station that is m stations ahead from the current station. So if current station is S, target is S+m.
The rabbit has tickets that allow him to move to certain stations? Or to travel a certain distance? "you can use the k ticket to go to p⋅ak + q⋅bk station." Could be interpreted: using ticket k, the rabbit goes to the station that is pa^k + qb^k (i.e., the station number equals that value). But then the current station is not defined; maybe the rabbit can start from station 0? Usually in such problems, you start from 0, and you have tickets that allow you to jump to certain positions. The target is at position m. The rabbit wants to reach exactly m, but he can also walk? "wants to walk as short as possible." So perhaps the rabbit can use a ticket to go directly to some station (maybe the ticket takes him to that station, not relative). Then he can walk the remaining distance to m. He wants to minimize the walking distance. If he can exactly land on m, walking distance 0. Otherwise he may overshoot? Or can only go to stations via tickets? Possibly the rabbit can use only one ticket? Or can combine multiple tickets? The phrase "When using, how many stations can a rabbit walk to reach the store?" suggests after using the ticket(s), the rabbit may need to walk some stations to reach m. The goal is to minimize walking distance. Then the question: "Output the number of rabbits that can reach the store on foot at the minimum number of stations in one line." That sounds like: Among all tickets (k from 0 to n-1), each gives a destination station d_k = p * a^k + q * b^k. The rabbit, after using the ticket, will be at station d_k. Then he must walk to station m (the shop location). The walking distance is |d_k - m| (since stations are on a line). He wants to minimize this distance over all k. Then the output is the number of tickets (i.e., number of k) that achieve this minimum distance.
But wait: The phrase "the number of rabbits that can reach the store on foot at the minimum number of stations" could be interpreted as: there are many rabbits? Actually it says "I have n tickets for a train with a rabbit." So maybe one rabbit? Or "rabbit" is a character? Alternatively, could be: There are n tickets, each for a rabbit? That seems off.
Let's read the original: "I have n tickets for a train with a rabbit. Each ticket is numbered from 0 to n − 1, and you can use the k ticket to go to p⋅ak + q⋅bk station.
Rabbit wants to go to the all-you-can-eat carrot shop at the station m station ahead of the current station, but wants to walk as short as possible. The stations are lined up at regular intervals. When using, how many stations can a rabbit walk to reach the store?"
Maybe it's a translation: Possibly "rabbit" is something like "rabbit" as a means of transportation? Actually "train with a rabbit" might be a metaphor: maybe "rabbit" refers to a hopping method? Or "Rabbit" is a name.
Given typical competitive programming problems: There is a function f(k) = p * a^k + q * b^k. Given n, m, a, b, p, q, find among k=0..n-1 the minimal absolute difference |f(k) - m|, and output how many k achieve that minimum.
The examples:
Input: 6 200 2 3 4 5 Output: 1
Compute f(k) = 4 * 2^k + 5 * 3^k? Since p=4, a=2, q=5, b=3? Actually input: "6 200 2 3 4 5". According to order: n=6, m=200, a=2, b=3, p=4, q=5? Possibly the order: first n, then m, then a, then b, then p, then q. So a=2, b=3, p=4, q=5. Then f(k) = pa^k + qb^k = 42^k + 53^k.
Let's compute for k=0..5: k=0: 41+51=9 k=1: 42+53=8+15=23 k=2: 44+59=16+45=61 k=3: 48+527=32+135=167 k=4: 416+581=64+405=469 k=5: 432+5243=128+1215=1343
Now m=200. Differences: |9-200|=191 |23-200|=177 |61-200|=139 |167-200|=33 |469-200|=269 |1343-200|=1143 Minimum is 33 at k=3. Only one k achieves min => output 1. That matches.
Second example: Input: 6 1 2 3 4 5 => n=6, m=1, a=2, b=3, p=4, q=5. f(k) as above: [9,23,61,167,469,1343]. Differences: |9-1|=8, |23-1|=22, |61-1|=60, |167-1|=166, |469-1|=468, |1343-1|=1342. Minimum is 8 at k=0 only. So output 1. That matches.
Thus interpretation seems correct.
So problem: Given n, m, a, b, p, q (all up to 1e12, i.e., 10^12). Compute f(k) = p * a^k + q * b^k for integer k from 0 to n-1. Find min |f(k)-m| and count number of k achieving it.
But careful: n can be up to 1e12, so we cannot iterate over all k. We need to handle large n efficiently. Also a,b,p,q up to 1e12, m up to 1e12. So values can become extremely large (exponential). However n is huge, so for many k, f(k) will be enormous, far from m. The minimal difference likely occurs for small k because f grows exponentially. But n could be small too. Since n up to 1e12, we can't iterate over all k; but maybe the function grows so fast that only few k near the point where f(k) crosses m are relevant. Indeed, f(k) is monotonic increasing if a,b >= 1 and p,q >= 1? But a,b,p,q are positive integers? Input says 1 ≤ all, so yes positive. So f(k) is strictly increasing because a,b >=1? Actually if a=1 or b=1, it might not be strictly increasing? Since a,b >=1, but a=1 or b=1 would still yield non-decreasing? Let's see: f(k) = p * a^k + q * b^k. If a=1 and b=1, then f(k)= p+q constant. If a=1, b>1 then f(k) = p1^k + qb^k = p + q*b^k, increasing because b>1. If a>1, b=1 similar. So generally f(k) is non-decreasing; if both a=1 and b=1, constant. But since m can be up to 1e12, constant case is simple.
Thus we can find the k where f(k) is closest to m. Because f grows quickly, we only need to examine k in a small range around the crossing point. However, n can be large, so we need to consider that k is bounded by n-1. So the candidate ks are from 0 to n-1, but we only need those where f(k) is near m. Since f grows exponentially, for large n the function values become huge, but if m is also huge (up to 1e12) and a,b can be as small as 1? For a=1,b=1, f is constant, all ks have same f. For a=1,b=2? Then f(k)= p1 + q2^k = p + q*2^k. With p,q up to 1e12, f(k) can exceed 1e12 for modest k. For a and b possibly 1? Actually a and b are at least 1, but they can be 1. If both are 1, f(k)=p+q constant. If one is 1 and the other 1, constant. If one is 1 and the other >1, f grows exponentially due to the other.
If both a and b are >1, f grows doubly exponential? Actually it's sum of two exponentials; the dominant term is the larger base. If a and b are both >1, f grows roughly like max(p a^k, q b^k). So it's exponential with base max(a,b). For base as small as 2, f(k) ~ constant * 2^k. For m=1e12, k ~ log2(1e12) ≈ 40. So k is at most about 40 for typical parameters. But if a=b=1, then k can be huge but f is constant, so all k give same distance. But then we need to count how many k (i.e., n) achieve that distance? Since all give same |constant - m|, the min is that distance, and count = n (since all k 0..n-1 achieve the same). But careful: if the constant is exactly m, then distance 0 and count = n. If constant ≠ m, distance is |constant - m|, and all k give same distance, so count = n. So for a=b=1, answer is n (if n>=1). But is n up to 1e12? That's fine to output.
If only one base is 1, say a=1, b>1. Then f(k) = p + qb^k. This is increasing for k>=0? Since b>1, qb^k increases, so f(k) strictly increasing. It may cross m at some k. For large k, f(k) huge. So the closest point is near the k where q*b^k ≈ m - p. So k ≈ floor(log_b((m-p)/q)). That's about O(log m). So again small.
If both >1, same.
Thus, in most cases, the function grows quickly, so the number of relevant k is O(log m) which is at most about 40-50 for m up to 1e12. However, careful: a and b could be 1 as well. Also a and b could be =1 but not both? Then f(k) = p1 + qb^k. For b=1 as well? Actually if a=1, b=1 both, then constant. If a=1, b>1, fine. If a>1, b=1, symmetric.
But also a and b could be less than 1? No, they are >=1. So all positive integers.
But there is another nuance: p and q up to 1e12, so f(0) = p+q could be up to 2e12, already > m if m is 1e12. So the closest may be at k=0. So we need to consider small k from 0 upward until f(k) exceeds m significantly and continues growing. Since it's increasing (if not constant or decreasing? It's non-decreasing; if a=1 and b=1 constant; if one base is 1 and the other >1, increasing; if both >1, increasing). So we can find the smallest k such that f(k) >= m (if any). Then the minimum distance will be among k = that index and previous index (if exists). Also need to consider if the function is decreasing? Could it be decreasing? a,b >=1, exponents are nonnegative, so a^k and b^k are non-decreasing as k increases (since base >=1). If base=1, it's constant; if base>1, increasing. So f(k) is non-decreasing. So the minimal distance will be attained at k where f(k) is closest to m, which is either at the largest k with f(k) <= m or the smallest k with f(k) >= m, or both if equal.
Thus we can compute f(k) for k=0,1,2,... until f(k) > m + current_min? Actually we can compute until f(k) becomes too large that further increments only increase distance. Since f is increasing, after passing m, f(k) continues increasing, so the distance |f(k)-m| = f(k)-m increases. So once f(k)-m > current best distance (i.e., minimal distance found so far), we can stop because for larger k it will only increase. However, we must be careful: if f(k) hasn't reached m yet, we need to go until it surpasses m and then maybe a bit beyond to see if crossing yields a closer point. But as soon as we pass m and the distance starts increasing, further k will have larger f(k), so distance increases. So we can stop after the first k where f(k) >= m and the distance f(k)-m > current best? Actually we need to compute best among those considered. The best is either at the last k before crossing or at crossing if equal. Suppose we compute sequentially for k=0,1,2,... and keep track of min distance. Once we have a k where f(k) >= m, the distance is f(k)-m. For the next k+1, since f(k+1) > f(k), the distance f(k+1)-m will be larger than f(k)-m (assuming f(k)>=m). So after the crossing, the distance monotonically increases. Thus we can stop after the first k where f(k) >= m, and then compare distance with previous k's distance. However, note that before crossing, the distance m - f(k) decreases as f(k) increases. So we can just find the k where f(k) is as close as possible: this is essentially binary search for the k such that f(k) is near m, but since f is integer and increasing, we can find the largest k with f(k) <= m, then consider k and k+1. But we have to ensure k is within [0, n-1]. Also if f(0) > m, then the min distance is at k=0.
Thus we need to compute f(k) for specific k values, but we cannot iterate all up to n-1 if n is huge (1e12). However we can compute f(k) quickly via fast exponentiation (but careful of overflow: values can become huge beyond 64-bit, but we only care about comparing with m up to 1e12, and also we may need to compute f(k) exactly for difference, but if f(k) exceeds m by a lot, we might not need exact huge values, we just need to know that it's > some threshold. So we can use early exit: if a^k or b^k become > (m + best) / p etc., we can cap.
But the bigger challenge: we need to find the k that minimizes distance among all valid k in [0, n-1]. Since f(k) is monotonic, the candidate ks are only those near the "crossing" point, but what if n is less than that crossing point? For example, if n is small, the maximal k is n-1, which might be less than the crossing point where f(k) would exceed m. Then the min distance might be at k = n-1. So we need to consider the bound n-1.
Thus we need to consider the interval of possible k: [0, n-1]. Since f is increasing, the distance as a function of k is decreasing until f(k) <= m, and increasing after f(k) >= m. So the minimum over the restricted domain is at either the largest k such that f(k) <= m (if exists) or the smallest k such that f(k) >= m (if exists). If f(k) is always <= m for all k in domain (i.e., f(n-1) <= m), then min distance is at k = n-1 (since distance decreasing as k increases? Actually if f(k) <= m, then distance = m - f(k) which is decreasing as f(k) increases, so the smallest distance is at the largest k, i.e., n-1). Similarly, if f(0) >= m, then min distance at k = 0.
Thus the problem reduces to: find the k in [0, n-1] that minimizes |f(k)-m|. Because f is monotonic, it's essentially to find the "closest" k, which is either the largest k with f(k) <= m or the next k (if <=n-1). But we must be careful: if both bases are 1, f is constant, so all k are equally close. But then the monotonic approach still works: f(k) constant, then both conditions hold; the distance is same for all, so count = n.
So we need to compute f(k) for a few candidate k: possibly k = 0, n-1, and the k where f(k) crosses m. But how to find crossing k efficiently? Since f(k) grows exponentially, we can binary search on k in range [0, min(n-1, Kmax)]? But we need to find the largest k with f(k) <= m. Since k may be up to n-1, but n can be huge (1e12). However f(k) for k ~ 1e12 is astronomically huge for a,b>1, but we can treat that as > m. So the crossing k is relatively small. The maximum possible k such that f(k) <= m can be bounded by log of m. For example, even if a=b=2, f(k) = p2^k + q2^k = (p+q)2^k. So k_max = floor(log2(m/(p+q))). With m up to 1e12, p+q up to 2e12, so k_max could be negative? Actually p+q may be > m, so f(0) may already > m. So k_max could be -1 (none). For a=1,b=2, f(k)=p + q*2^k. Then k_max = floor(log2((m-p)/q)) which is at most about 40. For a=1,b=1, f constant. So in all cases except constant, crossing k is O(log m). For a=1,b=1, we need special handling.
Thus we can find the candidate k_star = the largest integer k such that f(k) <= m, with k in [0, n-1]. But because n may be less than that, the largest k with f(k) <= m may be n-1 if f(n-1) <= m. So essentially we need to find:
- If f(0) > m, then min at k=0.
- Else, we find the largest k in [0, n-1] with f(k) <= m. Let that be k0 (could be n-1 if f(n-1) <= m). Then consider k0 and k0+1 (if k0+1 <= n-1). The min distance will be among these.
But what if f(k) is constant? Then f(k) <= m may hold for all k if constant <= m, else none. Actually constant <= m then f(k) <= m for all, so largest k with f(k) <= m is n-1, and f(k) = constant, so distance same for all. So min distance is constant and count = n. If constant > m, then f(0) > m, min at k=0 and all k same? Actually if constant > m, then f(k) > m for all, so distance = constant - m for all, so min is same for all, count = n as well. So for constant case, count = n.
But careful: If constant = m, distance 0, count = n.
Thus we can compute the number of k achieving minimal distance.
But is there any scenario where the minimum distance is achieved at multiple ks that are not just k0 and k0+1? For monotonic function, the distance |f(k)-m| as a function of k is convex (decreasing until crossing, then increasing). If f(k) is strictly increasing, then there can be at most two points achieving the same minimal distance: one on each side of m if distances are equal. But could there be more than two? Only if f(k) is constant over an interval, but f(k) is strictly increasing unless both bases =1. So at most two.
But we also must consider that the domain is limited to [0, n-1]. So the min could be at the endpoints. So the candidates are at most 3: k0 (largest <= m) and k0+1 (if exists), and possibly also k0-1? Actually if f(k) is strictly increasing, then distance for k < k0 is larger than for k0 because f(k) < f(k0) <= m, so distance = m - f(k) > m - f(k0) (since f(k) smaller). So k0 is the best among those <= m. Similarly, for k > k0+1, distance = f(k)-m > f(k0+1)-m if f(k0+1) is the smallest >= m. So only k0 and k0+1 are candidates (plus endpoints if k0 is not defined because all f(k) > m, then only k=0; or all f(k) <= m, then only k = n-1). So at most two candidates.
Thus algorithm:
- If a == 1 and b == 1: then f(k) = p + q constant. So distance = |p+q - m|. All k from 0 to n-1 have same distance. So answer = n.
- Else: f is strictly increasing (since at least one base >1). We'll compute f(k) for k up to some limit to find the crossing point within [0, n-1]. However n can be huge, but the crossing point (where f(k) >= m) is O(log m) as argued. But we must also consider the case where n-1 is smaller than the crossing index, i.e., f(n-1) <= m. Then the candidate is k = n-1 only. But we need to compute f(n-1) to check if it's <= m. However n can be up to 1e12, but if n is huge, f(n-1) would be astronomically huge if a,b >1? Wait, if n is huge, say n = 1e12, and a,b >1, then f(1e12) is incomprehensibly large, certainly > m (since m <= 1e12). So for n huge, the crossing point is far less than n-1. So in practice, n-1 is likely much larger than crossing point. But we cannot assume that; n could be small, e.g., n=5, a=2,b=3, then crossing might be at k=3 etc. So we need to handle both.
Thus we need to compute f(k) for k up to min(n-1, K_max) where K_max is some bound beyond which f(k) > m and distance only increases. Since f grows quickly, K_max is small (like <= 60 for 64-bit). But what if a=1,b=1? Already handled. If a=1,b>1, then f(k) = p + q * b^k. For b=2, k can be up to about 40 before exceeding 1e12. For b=1? Already covered. If a>1,b=1 symmetric. If both >1, k even smaller because growth faster. So indeed, for m up to 1e12, k_max is at most about 60 (if b=2 and p,q =1). Even if p and q are 1, b=2, then f(k) = 2^k + something. 2^40 ≈ 1e12, so k up to 40. If a=1,b=1, constant.
Thus we can iterate k from 0 upwards while k <= n-1 and while we haven't exceeded m by a large margin? Actually we can find the largest k such that f(k) <= m, by starting from k=0 and incrementing until f(k) > m or k reaches n-1. But this could be up to 40 iterations, which is fine.
But careful: There is a scenario where n is small but crossing point is beyond n-1, i.e., f(n-1) <= m. In that case, we need to compute f(n-1) to confirm. Since n could be as large as 1e12? But if n is large, then f(n-1) is huge, so crossing point is small. However there is possibility that both a and b are 1? Already constant. Or a=1,b=1? constant. Or a=1,b=1? Actually both =1 gives constant. Or a=1,b=1? That's constant. Or if a=1 and b is also 1? That's the same. So for non-constant case, growth is exponential, so for n huge, f(n-1) enormous, thus crossing point is small. So the only case where n-1 is less than crossing point is when n is small, e.g., n=5, a=2,b=3, m=1000, f(4)=469 <=1000? Actually f(4)=469, f(5)=1343 >1000, so crossing at k=5, but n-1=4? If n=5, then k max=4, and f(4)=469 < m, so all f(k) <= m. So min at k=4. That's fine; we need to compute f(4). n is small, computing f(4) is trivial.
Thus we can iterate k from 0 up to min(n-1, some bound like 60 or maybe until f(k) > m and also k <= n-1? But if n-1 is larger than crossing point, we will stop after crossing because further k only increase distance. But we need to also consider the possibility that after crossing, the distance might become smaller again? No, monotonic increasing.
Thus we can do:
Initialize best_dist = infinity, best_count = 0. For k from 0 while k < n and (maybe we break condition): compute d = f(k) dist = abs(d - m) if dist < best_dist: update best_dist = dist, best_count = 1 else if dist == best_dist: best_count++
But we cannot loop up to n if n huge (1e12). However we expect to break early because after some k, d becomes huge and dist keeps increasing. But we need to guarantee that after some point, dist will never be less than current best. Since f is increasing and m is fixed, once we have passed m and the distance is increasing, and we have already recorded the minimum from before crossing, we can stop because further k will only give larger distances. However we must also consider the case where we haven't yet reached m: distance is decreasing as k increases. So we need to continue until we either exceed m or reach n-1. But if n is huge and f(k) grows slowly? But if f grows slowly? Wait, f(k) = pa^k + qb^k. Since a,b >=1, the only way it grows slowly is if a and b are both 1 (constant). Already handled. If one base = 1 and the other = 1? That's constant. If one base = 1 and the other = 1? That's constant. If one base = 1 and the other >1, growth is exponential with base >1, so eventually it surpasses m quickly. However there is scenario where a=1 and b is also 1? constant. Or a=1 and b is also 1? constant. So only constant case leads to slow growth. But what if a=1 and b is slightly >1, say b=2, but p and q are huge? f(k) = p + q2^k. If p is huge, say p=1e12, q=1, then f(0)=1e12+1, maybe > m? If m is also 1e12, f(0) could be close. But as k increases, f(k) increases because q2^k grows. So it will exceed m further. So minimal might be at k=0. So we need to compute f(0) anyway.
If p and q are huge, f(0) could be > m. Then we might have f(0) > m, and f(1) even larger. So distance increases with k, so min at k=0. So we can break after evaluating k=0? But we need to be sure that for k=1, distance is larger. Since f is increasing, yes. So we can break after k=0 if f(0) > m? Actually if f(0) > m, then for k>0, f(k) >= f(0) > m, so distance = f(k)-m >= f(0)-m, with equality only if f(k)=f(0) (which requires a=b=1). So if not constant, distances strictly larger. So min at k=0 only. So we can break. So we can stop after k=0 if f(0) > m and a,b not both 1. But if a,b both 1, constant, we already handled.
Thus the only case where we need to iterate many steps is when f(0) <= m and we need to find where f(k) surpasses m. But as argued, number of steps is O(log m) which is at most about 60. So iterating from k=0 upward until f(k) > m or k reaches n-1 is acceptable because we will break early.
But is there any scenario where f(k) never exceeds m within n steps? That would require that f(n-1) <= m. Then we would have to iterate all the way to n-1. But n could be huge (1e12) and f(n-1) <= m? For that to happen, f(k) must be bounded by m for k up to 1e12. Since f(k) is increasing (non-constant), it grows without bound (unless a=b=1). So for it to stay <= m for huge n, growth must be extremely slow, but with a,b >=1, if any base >1, f(k) grows exponentially, so for n huge, f(n-1) will be astronomically huge, far exceeding m. Therefore the only way f(n-1) <= m is if n-1 is small (i.e., n itself is small). But n can be up to 1e12, but if it's huge, then f(n-1) is definitely > m (since exponential). So we wouldn't need to iterate all the way to n-1; we would stop far earlier when f(k) > m. Conversely, if n is small (e.g., n <= 60), iterating up to n-1 is fine. So overall, the loop will have at most about O(log m) iterations, which is safe.
But wait, what if a=1 and b=1? constant, we handled separately. What if a=1, b=1? constant. What if a=1, b=1? Yes.
What about a=1, b=1? Already constant. But what if a=1 and b=1? Exactly.
What about a=1, b=2, p=1e12, q=1e12? f(0)=2e12 > 1e12, so we stop at k=0. Good.
Thus straightforward loop over k from 0 to min(n-1, maybe 60 or until condition) works.
But careful: For a=1, b>1, f(k) = p + q*b^k. This grows exponentially. So after a few steps, it surpasses m. So loop up to maybe 60.
But what if a and b are both 1? Already constant.
Thus algorithm seems trivial: just iterate k from 0 to n-1, break when k exceeds some threshold where f(k) > m and f(k) - m > current best (which would be m - f(k-1) if f(k-1) <= m) and also further increments only increase. However to be safe, we can do:
- If a == 1 and b == 1: answer = n.
- Else: best_dist = large (e.g., 10^19) best_cnt = 0 prev_dist = None for k in range(0, n): compute d = f(k) with overflow handling: if d exceeds some large bound (greater than m + best_dist) we can break because further k will have even larger d. But we must compute d exactly if it's not too large to compare? Actually we can compute d using 128-bit integers (e.g., Python big ints fine). Since numbers can be huge (like (1e12) * (2^(1e12)) insane) but we will break early before they become astronomically large. So in Python, big integers can handle arbitrary size but computing such huge numbers would be impossible if we attempt to compute a^b for huge exponent. But we will break early because we stop when k exceeds some threshold where f(k) > m and distance only grows. But the exponent k itself will be at most maybe 60, so we can compute a^k, b^k exactly with pow, which is fine. Even if n is huge, we will not iterate beyond k where f(k) > m and we see distance increasing. Since exponential grows fast, k will be small. However we need to ensure that we don't accidentally iterate beyond that due to n huge; we break when condition met.
But what if for some parameters, f(k) never exceeds m? Only constant case. So safe.
Thus we can implement:
def f(k): return p * (ak) + q * (bk)
But careful: ak and bk could be large, but k is small (<=60). However if a and b are 1e12, then a**k can be huge even for k=2: 1e24, which still fits in Python big ints, but might be large. But it's fine.
But wait: what if a=1, b=1? constant case we already handled, so we avoid exponent. For a=1, b>1, then a**k = 1, fine. For a>1, b=1, similarly.
But there is a subtlety: if a and b are both 1? constant.
But what about a=1, b=1? That's constant.
Now, we need to determine the break condition: while k < n and (some condition). We want to stop when we have passed m and the current distance (d - m) is greater than the best distance found so far. But best distance so far might be from the previous k (which was <= m) if it exists. However if we haven't found any k with d > m yet, we continue until d > m. After we find first d > m, we can compare its distance with previous (d_prev <= m). The minimal distance will be either at prev_k or this_k. After that, for larger k, d will be even larger, so distance will increase. So we can break after evaluating k that first exceeds m and also after evaluating the next k? Actually we can break after checking k that first exceeds m, because we know for any later k, distance > current d - m, and we already have the best from prev_k (which may be closer). However we need to be sure that no later k could have distance equal to current d - m? Could two different ks have same distance? If d - m is the same as m - prev_d? Only if they are symmetric around m. That would be only two ks: the one below and the one above. After that, distances only increase. So after we have evaluated k0 (largest <= m) and k0+1 (first > m), we can break. So we can identify k0 (the last k with f(k) <= m). So we can find k0 by iterating until f(k) > m or k == n-1.
Thus we can:
if a == 1 and b == 1: print(n) return
k = 0 while k < n: d = compute f(k) dist = abs(d - m) # update best if dist < best_dist: best_dist = dist; best_cnt = 1 elif dist == best_dist: best_cnt += 1 # if d > m and k > 0? Actually once d > m, we know that for any later k, d will be larger, so distance will be larger (since strictly increasing). So we can break after this iteration, but we still need to consider that there might be later k where distance equals best_dist? Only if d - m equals best_dist again. But if best_dist is currently from the current d (which is > m) and we have not yet seen a smaller distance from previous k, then later distances will be larger than d - m (since d increases) so they cannot equal best_dist unless they are equal to d - m exactly? But if d - m is some value, and later d' > d, then d' - m > d - m, so cannot equal. So best_dist from current d will be unique. If best_dist came from previous k (which was <= m), then later distances are > current d - m, and current d - m may be larger than best_dist or equal. If current d - m == best_dist (i.e., equal to distance from previous k), then both have same distance. For later k, distances increase, so they cannot equal best_dist. So we can break after processing k (the first k with d > m). But we must also consider the possibility that there is no k with d > m within n (i.e., all f(k) <= m). Then we cannot break early; we have to continue until k == n-1. But as argued, if n is huge and all f(k) <= m, then f(k) grows unbounded; it's impossible for all f(k) <= m unless f is constant or n is small enough that the largest k is before crossing. So if n is huge, we will encounter d > m at some small k. So we will break early.
But wait: what if a=1, b=1 constant, already handled. What if a=1, b>1? Then f(k) = p + q*b^k. This grows, so eventually > m. If n is so small that the maximum k (n-1) is still below the crossing point, then we must iterate all k up to n-1. But n is small (like <= 60), so it's fine.
Thus algorithm: iterate k from 0 up to min(n-1, some bound) but we can just use while loop with break condition.
Implementation details:
We need to compute f(k) efficiently for k up to maybe 60. But note that k could be 0,1,2,... up to n-1, but we break early. However there is a corner case: if n is huge (1e12) but a and b are both 1? Handled separately. If a and b are such that f(k) grows very slowly? Is it possible for f(k) to grow sub-exponentially? Since a and b are integers >=1, if a=1 and b=1, it's constant. If a=1 and b=1, constant. If a=1 and b>1, f(k) = p + q*b^k, which is exponential. If a>1 and b=1, similar. If a>1 and b>1, it's exponential. So growth is at least exponential with base min(a,b) that >1? Actually if one is 1, growth is exponential in the other base. So it's at least exponential with base >=2? Not necessarily: if a=1 and b=2, base 2. But b could be 1? No, b>1 if a=1? Actually b could be 1 as well? But if a=1 and b=1, constant. So non-constant cases have at least one base >1, so growth is at least exponential with base >1. So indeed after O(log(m)) steps, f(k) surpasses m.
But what about p and q being zero? Input says 1 ≤ everything, so positive.
Thus the loop is safe.
But we must be careful about overflow in languages with fixed-size integers. In Python, big integers fine.
Now, we need to compute count of k achieving minimum. But we only evaluate a few ks? What if there are more than two ks achieving the same minimum? For non-constant strictly increasing f, the distance function |f(k)-m| is strictly decreasing for k < k* where f(k) < m, and strictly increasing for k > k* where f(k) > m, with k* being the point where f(k) crosses m. So it is convex (V-shaped). Thus there can be at most two values that achieve the same minimum: one on each side if distances are equal. Could there be a plateau where f(k) equals m for multiple consecutive k? Since f is strictly increasing (if not constant), f(k) cannot equal m for more than one k. So the minimum distance could be achieved at a single k (if f(k)=m exactly, then distance 0, only that k) or at two ks (if distances on both sides equal). So count is either 1 or 2 (or n in constant case). However, could the minimum occur at the endpoints (0 or n-1) and also some interior? Possibly if the distance at endpoint equals distance at interior? That could happen, e.g., if f(0) is closer than all others? But then only that endpoint. If f(0) distance equals f(1) distance? That could happen if they are symmetric around m. But since f is strictly increasing, f(0) and f(1) are distinct. So if m is exactly halfway, they could have equal distance. So two points.
But what about the case where n is huge but the crossing point is within domain and we break after k0+1. That's fine; we have considered k0 and k0+1. But what about k0-1? That would be further from m than k0 because f(k0-1) < f(k0) <= m, so distance larger. So no need.
But wait: what if f(0) > m? Then we only evaluate k=0, get distance, and we break? Actually we could break after k=0 because we know for k>0 distance larger. But we must be careful: if f(0) > m, we should still check k=1? But f(1) > f(0) > m, so distance f(1)-m > f(0)-m. So indeed min at k=0. However, we need to ensure there is no k where distance equals f(0)-m besides k=0. Could there be another k with same distance? If f(k) - m = f(0) - m, then f(k) = f(0), which would imply pa^k + qb^k = p + q. Since a,b >=1 and at least one >1, for k>0, f(k) > p+q (unless a=b=1). So strictly larger. So no. So only k=0.
Thus break after k=0 if f(0) > m. But to keep code simple, we can just loop with break condition: if d > m and (k > 0 and d - m > best_dist): then break. But we need to ensure we have considered the candidate on the left side. Actually after we encounter d > m, we should still check if d - m == best_dist maybe. Then we break after that iteration. However we also need to consider if there might be a later k where d - m equals best_dist? As argued, distances increase, so if best_dist is from d (the first > m), then later distances larger; if best_dist from earlier (<= m), then d - m is either > best_dist or = best_dist. If >, break; if =, then after break we have considered both. So we can break after processing the first d > m. Because subsequent ones will be larger. But careful: what if the first d > m is at k=0? Already covered.
One more nuance: The distance could be minimized at some k beyond the first d > m if there is a later k where d becomes closer again? That can't happen because d is strictly increasing, so after crossing m, d only moves away from m (unless m is exactly between two values? No, it moves further). So no.
Thus algorithm stands.
Edge Cases:
-
n=1: Only k=0. Compute distance, output 1.
-
a=1,b>1: f(k)=p + q*b^k. This is increasing. Good.
-
a>1,b=1: symmetric.
-
a=1,b=1: constant.
-
Large numbers: computation of a^k and b^k for k up to maybe 60. But a and b can be up to 1e12, so a^60 is (1e12)^60 = 10^(1260) = 10^720, a ridiculously huge number. But Python can handle big integers, but performing exponentiation on such large numbers may be extremely slow and memory intensive? However, we will break before k becomes that large because f(k) will exceed m (1e12) long before k=60 if a or b is huge. For example, if a = 1e12, then a^1 = 1e12, already possibly > m. So we may only need k=0,1. So we should not compute a^60 when a is huge. Our loop will compute f(k) incrementally: we can compute a^k iteratively by multiplying a each step. But if a is 1e12, a^1 = 1e12, maybe still <= m if p and q small? m can be up to 1e12, so f(1) could be p + q * b^1, etc. But for a^2 = 1e24, definitely > m. So we will break after k=1 or maybe k=2 at most. So exponentiation won't go to huge exponents. But we need to be careful when computing a^k directly with pow could be expensive for large exponents even if the result is huge; but we can compute iteratively and break early if the term exceeds some threshold? Actually we need the exact value of f(k) to compare with m and to compute distance exactly. But if f(k) becomes astronomically huge, we might not need exact value; we only need to know that it's > m and that subsequent distances are larger. However, we also need to check if there might be a tie? But if f(k) is huge, distance huge, not min. So we could cap computation to avoid huge numbers. But in Python, big ints are okay for numbers up to maybe a few hundred digits. But if a=10^12 and k=10, a^k has 1210+1 = 121 digits, still fine. k=20 gives 241 digits, still fine. But if a=10^12 and b=10^12, and k=10, f(k) would be (p+q)*(10^12)^10 = (p+q)*10^120, which is 120+ digits. Python can handle that. However, if we mistakenly compute for k up to 60, a^60 gives 720 digits, still manageable (though maybe slower but okay for one test? There may be multiple test cases? Problem doesn't specify number of test cases; likely just one. So it's okay.
But we have to ensure that we don't loop up to n-1 when n is huge but we break early. However, consider a scenario where a=1, b=2, p=1, q=1, m=1e12. Then f(k) = 1 + 2^k. 2^40 ≈ 1e12, so k around 40. So we compute up to k=40, which is fine.
What about a=1, b=1? handled.
What about a=2, b=3, p=1, q=1, m=1e12. f(k) = 2^k+3^k. 3^24 ≈ 2.8e11, 3^25≈8.5e11, 3^26≈2.5e12, so k ~ 25. Fine.
Thus loop size is small.
But there is another scenario: a and b are both 1? constant.
Now, could there be a case where f(k) grows so slowly that we need to iterate many k before surpassing m? That would require a and b both being 1, which is constant. If one is 1 and the other is 1? Actually a=1,b=1 is constant. If a=1,b>1, it's exponential, so k logarithmic. If a>1,b>1, also exponential.
Thus safe.
Therefore, simple solution: iterate k from 0 to n-1, compute f(k) via pow (or iterative multiplication), update best, break when d > m and d - m > best_dist (or when k > 0 and d > m). But careful: if best_dist is not yet set from a point below m? Actually we need to ensure we have considered the point below m. Suppose we start with k=0, d0 <= m. We continue increasing k. For each k, we compute d. When we first encounter d > m, we compute dist = d - m. At that point, best_dist could be from previous k (which was <= m) or from this d if it's smaller. After that, we know for any larger k, d' > d, so d' - m > d - m. So if best_dist <= d - m, we can break. But if best_dist > d - m (i.e., current d gives better distance), then best_dist = d - m. But then for larger k, distances will be larger, so we can break after this iteration as well. So we can break after first d > m regardless? Let's examine:
- If d_prev (largest <= m) exists and distance_prev = m - d_prev.
- d_curr = first > m, distance_curr = d_curr - m. The minimum among all k <= curr is min(distance_prev, distance_curr). For any k > curr, d > d_curr, so distance > distance_curr. So if distance_curr <= distance_prev, then best is distance_curr, and later distances are larger, so break after curr. If distance_prev < distance_curr, then best is distance_prev, and later distances are > distance_curr > distance_prev, so break after curr. If equal, best is both, later distances larger. So in all cases, after processing the first k where d > m, we can break. However, we need to make sure we have processed the previous k (the one before crossing). That's done because we iterate sequentially, so we processed all k up to crossing. So we can break after the first d > m (including if that happens at k=0? Actually if f(0) > m, then d > m at k=0, there is no previous k. Then for k>0, distances larger, so break after k=0.)
Thus break condition: after computing d for current k, if d > m: after updating best, break.
But wait: What if we haven't yet processed all k up to n-1, but we break after first d > m? That's fine because later ks will have larger distances. However, we must be cautious: Is it possible that after some k, d becomes > m, but later due to some weird behavior (like a or b being 0? Not allowed), d continues increasing, so distances increase. So yes.
But what about the scenario where f(k) never exceeds m because n-1 is less than crossing point? Then we will never encounter d > m within the loop; we will iterate all k from 0 to n-1. That's okay; we'll process all.
Thus algorithm:
if a == 1 and b == 1: print(n) return
best_dist = None (or very large) best_cnt = 0
for k in range(0, n): # but n can be huge, so we need to loop with condition break. compute d = p * (ak) + q * (bk) # but we should compute iteratively to avoid huge exponents recomputed each time.
But we cannot iterate up to n if n is huge; we rely on break when d > m. So we need a while loop with k variable.
We'll start k=0, compute d0. If d0 > m, then best = d0-m, cnt=1, break.
Otherwise, we continue k=1,2,... until either k == n-1 or d > m.
But we also need to be careful about overflow: ak may become astronomical for moderate k if a is large. However, if a is huge (like 1e12), then at k=1, a1 = 1e12, times p up to 1e12 yields 1e24, which may already be > m. So we break at k=1. So it's fine.
But what about computing a**k for k up to maybe 60 with a=1e12? That's 10^720, which Python can handle but may be a bit heavy but okay. However, we can avoid huge numbers by early exit: if during computation we see that a^k > (m + best_dist) // p (or something) we can treat d as > m and break? But we need exact distance if it's candidate for min. But if d is huge, it can't be min if we already have a candidate with distance <= some bound. However, to keep it simple, we can compute exactly with Python's big ints; it's fine because the numbers we'll actually compute (before break) are not astronomically huge because we break when d exceeds m, and m is 1e12, so d will be at most maybe a few orders of magnitude larger. For a=1e12, d at k=1 could be pa + qb. If p and q are 1e12, d could be 1e121e12 + 1e121e12 = 2e24, which is 2*10^24, which is 25 digits, still fine. At k=2, a^2 = 10^24, times p=1e12 => 10^36, plus similar, that's 10^36 (36 digits). Still fine. At k=3, 10^48 digits, etc. So numbers could become large but not insane, and we break early. The worst-case number of iterations before break when a and b are close to 1? But then growth is slow, so k may be up to 40, and a and b are small (like 2), so numbers are moderate (2^40 ~ 1e12). So overall numbers are within reasonable size.
Thus we can compute directly.
Implementation details:
We'll read six integers: n, m, a, b, p, q.
We need to handle possibly large n (1e12) but we only loop a few times.
Pseudo:
def solve(): import sys n,m,a,b,p,q = map(int, sys.stdin.read().split()) if a == 1 and b == 1: # f(k) constant = p+q # distance = abs(p+q - m) # all k have same distance, so answer = n print(n) return
best_dist = None best_cnt = 0 # We'll compute iteratively: keep a_pow = a^k, b_pow = b^k a_pow = 1 b_pow = 1 k = 0 while k < n: d = p * a_pow + q * b_pow dist = abs(d - m) if best_dist is None or dist < best_dist: best_dist = dist best_cnt = 1 elif dist == best_dist: best_cnt += 1 # if d > m, we can break because further k will only increase d, thus increase distance (since d will be > m) if d > m: # But need to ensure that there is no later k where distance becomes equal to best_dist due to symmetry? No. # However, what if best_dist came from some earlier k and the current d gives larger distance? Then later are larger. # If current d gives smaller distance than earlier, later are larger. # So break. break # Prepare next k k += 1 if k == n: # reached end break # Update powers, but be careful of overflow? Not needed. a_pow *= a b_pow *= b print(best_cnt)But is this correct? Let's test with examples.
Example1: n=6,m=200,a=2,b=3,p=4,q=5. k=0: d=9, dist=191, best_dist=191,cnt=1; d>m? no. k=1: a_pow=2,b_pow=3,d=42+53=8+15=23,dist=177, <191 => best_dist=177,cnt=1. k=2: a_pow=4,b_pow=9,d=16+45=61,dist=139 -> best=139,cnt=1. k=3: a_pow=8,b_pow=27,d=32+135=167,dist=33 -> best=33,cnt=1. k=4: a_pow=16,b_pow=81,d=64+405=469,dist=269 (d>m) -> update? dist=269 > best=33, so cnt unchanged. Then check d>m: true, break. So best_cnt=1. Output 1. OK.
Example2: n=6,m=1,a=2,b=3,p=4,q=5. k=0: d=9,dist=8, best=8,cnt=1; d>m? 9>1 => break. So best_cnt=1. OK.
Now consider case where the minimum is achieved at two ks. For instance, suppose f(k) values: [2,4,6,8], m=5. Then distances: 3,1,1,3. Min distance=1 at k=1 and k=2. Our algorithm: k=0: d=2,dist=3,best=3,cnt=1; d>m? 2>5? no. k=1: d=4,dist=1,best=1,cnt=1; d>m? 4>5? no. k=2: d=6,dist=1, equal to best => cnt=2; d>m? 6>5 => break. So we break after k=2, but we haven't considered k=3? For k=3, d=8,dist=3 > best, so it wouldn't be counted anyway. So we have counted both minima. Good.
Now consider case where the minimum is at the last k and all f(k) <= m. Example: n=5, m=100, a=2,b=3,p=1,q=1. f: [2,5,13,35,97? Actually compute: k=0:2, k=1:2+3=5, k=2:4+9=13, k=3:8+27=35, k=4:16+81=97]. All <=100. The distances: 98,95,87,65,3. Min at k=4 (dist=3). Our loop would go through k=0..4 because d never > m (since 97<100). We process all, best at k=4, cnt=1. Then after k=4, we increment k to 5, but k==n so loop ends. So correct.
Now consider case where f(0) > m and we break at k=0. That's fine.
Now consider constant case a=b=1: f(k)=p+q constant. Our loop would treat as non-constant? Actually a=1,b=1 => f(k)=p+q. Our loop would compute k=0: d = p+q, dist = |p+q-m|, best set. Since d > m? maybe not. Then next k: a_pow=11=1, b_pow=11=1, d remains p+q, same. So we would continue iterating k=1,2,... and never break because d never changes and d > m? Could be if p+q > m, then d > m for all k, so d > m from start, and we would break at k=0? Actually if p+q > m, then d > m at k=0, we break after k=0. That would give best_cnt=1, but actually all n tickets have same distance, so answer should be n. So our algorithm would be wrong for constant case. Similarly, if p+q <= m, then d never > m, so we would iterate through all k from 0 to n-1, which could be up to 1e12, causing infinite loop. So we need to treat constant case separately. Indeed, a=1 and b=1 yields f(k) constant. So we handle that as special case: output n.
But what about a=1,b=1? Already covered.
Now, what about a=1,b>1 but p=0? Not allowed since p>=1.
Thus special case done.
Now, is there any scenario where a=1, b>1, but f(k) is constant? No, because b>1 => b^k increases.
Similarly a>1,b=1.
Thus algorithm works.
But we must be careful about overflow in the loop condition: while k < n. If n is huge (1e12) and we break early, fine. But if we don't break early (constant case we already handled, so non-constant will break early because eventually d > m). However, consider the possibility that a and b are both >1 but still f(k) never exceeds m within n iterations? That would require that n is so small that f(n-1) <= m. That's possible: e.g., n=5, a=2,b=3,p=1,q=1,m=1000, f(4)=97? Actually 2^4+3^4=16+81=97, still <1000, so f(4) <= m, and n=5? Actually n=5 means k max 4, so f(4)=97 <1000. So indeed f(k) never exceeds m within n. In this case, we will iterate through k=0..4 (n=5). That's okay because n is small (5). So we will not break early because d never > m. So loop runs n times, which is fine as long as n is small. Since n can be up to 1e12, but if n is large, then f(k) will exceed m for some small k, so we break early, and loop runs only a few iterations. So overall loop iterations are small (<= ~60). So it's safe.
But we must ensure that in the non-constant case, we will indeed eventually have d > m before k becomes too large, otherwise if a and b are both 1? Already excluded. But what if a=1 and b=1? Excluded. So for non-constant, f(k) eventually exceeds any finite m because it's unbounded. So there exists some K such that f(K) > m. That K might be large if growth is very slow. Could growth be sub-exponential? For integer bases >=1, the only way to have unbounded but slow growth is if one base equals 1 and the other equals 1? Actually if a=1, b>1, then f(k) = p + q * b^k, which is exponential in k, so it grows fast. So K is O(log_b(m)). If a>1,b=1 similar. If both >1, even faster. So K is at most about 60 for m=1e12. So safe.
Thus algorithm is O(log m) time.
Now we need to implement careful handling of large numbers. Use Python's big integers.
Edge Cases:
-
n could be 0? Input says 1 ≤ n, so n >=1.
-
m up to 1e12, but p and q up to 1e12, so f(0) = p+q up to 2e12. That's fine.
-
a,b up to 1e12, so a^1 up to 1e12, etc.
Potential pitfalls:
-
When a=1 and b>1, f(k) = p + q * b^k. At k=0, a_pow=1,b_pow=1. Updating: a_pow *= a (1), b_pow *= b (b). So a_pow remains 1, b_pow grows. That's fine.
-
When a>1 and b=1 symmetric.
-
When a=1 and b=1 special case.
Now consider case where a=1, b=1? Already special.
What about a=1, b=1 but we treat as non-constant? We'll special-case.
Now consider scenario where the best distance is achieved at two k's, and one of them is beyond the first d > m? That can't happen because after crossing, distances increase.
Now, we must also consider if there could be ties between k values where f(k) is exactly m? Then distance 0, only one k because strictly increasing.
Now, is there any possibility that the minimum distance occurs at k beyond the first d > m if the function is not strictly increasing? Could it be non-strict? If a=1 or b=1, but still strictly increasing? Let's examine: if a=1, b>1: f(k)=p + q*b^k. Since b^k is strictly increasing for k>=0 (b>1), f(k) strictly increasing. If a>1,b=1: similarly. If a>1,b>1: both terms increasing, strictly increasing. So yes, strictly increasing as long as at least one base >1. The only non-strict case is a=b=1 constant. So fine.
Thus our break condition is valid.
Now, what about the situation where d becomes exactly m at some k? Then distance 0. Our loop: when we compute d == m, dist=0. Then we update best. Then next iteration, d > m? Actually if d == m at k, then for next k, d > m (since strictly increasing). So after processing this k, we have d == m. The next k will have d > m, and after processing that (distance >0), we will break because d > m. But we must still process that next k? Actually if we break immediately after d > m, we would process that next k, update best (which will be larger), then break. That's fine. But if we break when d > m without processing the next? In our code, we compute d, update best, then check if d > m and break. So for the k where d == m, d > m is false, so we continue. For the next k, d > m, we process, then break. That's fine.
Now, ensure we handle the case where the first k (k=0) has d > m: we break after processing k=0. That yields best at k=0. Good.
Now, we must also consider if n is huge but we break early, we stop looping, which is fine.
Now, we need to be careful about the loop variable: we increment k and update powers after processing current k. But at the start, we set k=0 and compute with a_pow=1,b_pow=1. After processing k, we increment k and update powers for next iteration. But we need to ensure we don't go beyond n-1. Our while condition is while k < n: we process current k, then at end we do k += 1; update powers; but if k becomes n after increment, the loop condition will be checked at next iteration and fail. However, we also break after processing if d > m. In that case we should not increment further. So we must structure the loop correctly.
Simpler: Use for k in range(n): but range(n) with n up to 1e12 is impossible. So we use while loop with manual increment.
Alternative: we can compute the crossing point via binary search, but loop is fine.
Implementation details:
We'll maintain:
k = 0 a_pow = 1 b_pow = 1 while True: d = p