John Doe has a list of all Fibonacci numbers modulo 1013. This list is infinite, it…
- User
John Doe has a list of all Fibonacci numbers modulo 1013. This list is infinite, it starts with numbers 0 and 1. Each number in the list, apart from the first two, is a sum of previous two modulo 1013. That is, John's list is made from the Fibonacci numbers' list by replacing each number there by the remainder when divided by 1013.
John got interested in number f (0 ≤ f < 1013) and now wants to find its first occurrence in the list given above. Help John and find the number of the first occurence of number f in the list or otherwise state that number f does not occur in the list.
The numeration in John's list starts from zero. There, the 0-th position is the number 0, the 1-st position is the number 1, the 2-nd position is the number 1, the 3-rd position is the number 2, the 4-th position is the number 3 and so on. Thus, the beginning of the list looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Input
The first line contains the single integer f (0 ≤ f < 1013) — the number, which position in the list we should find.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
Output
Print a single number — the number of the first occurrence of the given number in John's list. If this number doesn't occur in John's list, print -1.
Examples
Input
13
Output
7
Input
377
Output
14
Assistant
We need to solve: Given f (0 ≤ f < 1013, but note f is integer between 0 and 1012 inclusive, modulo 1013). We need to find the smallest index n (>=0) such that Fibonacci number F_n mod 1013 = f, where Fibonacci numbers defined by F_0 = 0, F_1 = 1, and F_n = F_{n-1} + F_{n-2} mod 1013? Actually the problem statement: "John has a list of all Fibonacci numbers modulo 1013. This list is infinite, it starts with numbers 0 and 1. Each number in the list, apart from the first two, is a sum of previous two modulo 1013." So yes, the list is the sequence a_n = F_n mod 1013, with F_n being the usual Fibonacci numbers (F_0=0, F_1=1). So we need the smallest n s.t. F_n ≡ f (mod 1013). If f never occurs, output -1.
We need to compute Pisano period modulo m = 1013. Because Fibonacci sequence modulo m is periodic; the period is called Pisano period. For prime p ≠ 5, the period divides p−1 or 2(p+1) depending on Legendre symbol (5|p). Actually known: For prime p, if p ≡ ±1 mod 5, then period divides p−1; if p ≡ ±2 mod 5, period divides 2(p+1). But 1013 is prime? Let's check: 1013 is prime? 1013 is known to be prime? Let's verify: 1013 mod small primes: mod 2 no, mod 3: 1011 divisible by 3, 1013 mod 3 = 2; mod 5 = 3; mod 7: 7144=1008 remainder 5; mod 11: 1192=1012 remainder 1; mod 13: 1377=1001 remainder 12; mod 17: 1759=1003 remainder 10; mod 19: 1953=1007 remainder 6; mod 23: 2344=1012 remainder 1; mod 29: 2934=986 remainder 27; mod 31: 3132=992 remainder 21; mod 37: 3727=999 remainder 14; mod 41: 4124=984 remainder 29; mod 43: 4323=989 remainder 24; mod 47: 4721=987 remainder 26; probably prime. I think 1013 is prime. So we can use known properties.
But careful: Since m=1013, we need to find the Pisano period π(m). Then the sequence repeats after π(m). But also note that there might be occurrences of f before the period. So we can search up to period length to find minimal n. Since period length for primes can be up to O(m) ~ 1013? Actually for prime p, the period is at most 2p+2? Possibly larger. In general, Pisano period for prime p can be as high as p^2-1? Actually it's known that Pisano period modulo p divides p−1 if p ≡ ±1 mod 5, else divides 2(p+1). That's for primes. So for p=1013, compute p mod 5: 1013 mod 5 = 3, which is ≡ ±2 mod 5 (since 2 mod5 is 2, 3 mod5 is -2? Actually ±2 mod5 means 2 or 3). Yes 3 ≡ -2 mod5. So p ≡ ±2 mod 5, so Pisano period divides 2(p+1) = 21014=2028. That's an upper bound: the period is a divisor of 2028. That's small! Wait check: For primes p ≡ ±2 mod 5, period divides 2(p+1). For p ≡ ±1 mod5, divides p-1. This is known for Fibonacci period modulo prime. Actually more precisely: For prime p ≠ 5, the Pisano period π(p) divides p−1 if p ≡ ±1 mod 5, and divides 2(p+1) if p ≡ ±2 mod 5. This is based on the fact that the Fibonacci numbers are related to the multiplicative order of the matrix [[1,1],[1,0]] modulo p, and its eigenvalues are (1±√5)/2. The period is the order of that matrix, which relates to order of (1+√5)/2 in GF(p) or GF(p^2). So indeed for p ≡ ±2 mod 5, 5 is a non-quadratic residue modulo p, so the eigenvalues lie in GF(p^2), and the order divides p^2-1 = (p-1)(p+1). But a finer bound is p+1? Actually known: For p ≡ ±2 mod 5, the Pisano period π(p) divides 2(p+1). For p=7 (7 mod5=2), π(7)=16? Actually Pisano period for 7 is 16 (since 2(p+1)=16). For p=13 (13 mod5=3), 2(p+1)=28; π(13)=28? Actually Pisano period for 13 is 28? Let's check: I recall that π(13) = 28? Let's verify: Fibonacci mod13: 0,1,1,2,3,5,8,0,8,8,3,11,1,12,0,12,12,11,10,8,5,0,5,5,10,2,12,1,0,... Actually I'm not sure. Known: π(13)=28? The period often is 28 for 13. Yes π(13)=28. So 28 divides 2(13+1)=28, good. For p=3 (p=3, 3 mod5=3) 2(p+1)=8, π(3)=8? Actually π(3)=8? Let's check: Fibonacci mod3: 0,1,1,2,0,2,2,1,0,1,... period length 8. So indeed.
Thus for p=1013, π(1013) divides 2028. So the period is at most 2028, and it's a divisor of 2028. That's very small! We can simply compute Fibonacci numbers modulo 1013 up to maybe 2028, and record the first occurrence of each residue f. Since f is given, we can compute until we see f, but also we need to handle the case where f never occurs. But since the sequence is periodic and includes many residues, do all residues 0 ≤ f < 1013 appear? Not necessarily. Some residues might never appear. Actually it's known that the Fibonacci sequence modulo m is not necessarily surjective. For example, mod 5, residues: 0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,... So residues include {0,1,2,3,4} all appear? Let's check: 0 appears, 1 appears, 2 appears, 3 appears, 4 appears. So all appear mod5. For mod7: Fibonacci mod7: 0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,... I think residues: 0,1,2,3,4,5,6 all appear? 4 appears? In the list: ...5,4,2,6,... yes 4 appears. So all residues appear mod7. For mod11: I'm not sure. But maybe for primes the Fibonacci modulo p is surjective? Not necessarily. There's concept of "Fibonacci numbers modulo p" covering all residues? Actually it's known that for prime p, the Fibonacci sequence modulo p is periodic and the set of residues that appear can be less than p. For example, p=13: does residue 7 appear? Let's quickly check: Fib mod13: start: 0,1,1,2,3,5,8,0,8,8,3,11,1,12,0,12,12,11,10,8,5,0,5,5,10,2,12,1,0,1,... I see residues: 0,1,2,3,5,8,11,12,10. Did we see 4,6,7,9? Not yet. Might not appear? Continue: after that, it repeats? Actually period 28: sequence of 28 numbers: 0,1,1,2,3,5,8,0,8,8,3,11,1,12,0,12,12,11,10,8,5,0,5,5,10,2,12,1. So set: {0,1,2,3,5,8,10,11,12}. So residues 4,6,7,9 are missing. So not all residues appear for p=13. So for p=1013, some f may not appear.
Thus we need to compute the first occurrence within the period (or maybe beyond? Since it's periodic, if not in one period, it never appears). Actually careful: The sequence is purely periodic after some initial index? For Fibonacci modulo m, it is purely periodic from the start because the recurrence is deterministic and finite state: the pair (a_n, a_{n+1}) determines future and past. Since (0,1) appears at index 0, the sequence is periodic from start with some period π(m) such that (F_0, F_1) = (0,1) and (F_{π(m)}, F_{π(m)+1}) = (0,1). So the entire infinite sequence repeats that block of length π(m). So if f does not appear in the first π(m) terms (including index 0 to π(m)-1), it never appears. So we can compute all terms up to π(m) and record first occurrence. Since π(m) ≤ 2028, we can just simulate.
But is it guaranteed that π(1013) divides 2028? According to the theorem, yes, for prime p ≡ ±2 mod 5, the Pisano period divides 2(p+1). However, is that always true? I recall that for primes p ≡ ±2 mod 5, the period divides p^2-1, but a stronger bound is that it divides 2(p+1). Actually let's verify: Known fact: For a prime p ≠ 5, the Pisano period π(p) divides p−1 if p ≡ ±1 (mod 5), and divides 2(p+1) if p ≡ ±2 (mod 5). This is based on the relationship with the order of the Fibonacci entry point (the rank of apparition). However, I should confirm with some examples: p=2? p=2 mod5=2, 2(p+1)=6, but π(2)=3? Actually mod2: Fibonacci: 0,1,1,0,1,1,... period length 3, which divides 6. p=3 mod5=3, 2(p+1)=8, π(3)=8 divides 8. p=7 mod5=2, 2(p+1)=16, π(7)=16? Let's check: mod7: known Pisano period for 7 is 16. Yes. p=13 mod5=3, 2(p+1)=28, π(13)=28? Actually I think π(13)=28? There is known: π(13)=28. Yes. p=17 mod5=2, 2(p+1)=36, π(17)=36? Let's check: known Pisano for 17 is 36? Possibly. So bound holds.
Thus for p=1013, π(1013) is a divisor of 2028. But we need to compute the exact period? We don't need the period; we can simulate until we see (0,1) again. That is, start with a=0, b=1, and for n=0,1,2,... compute next, until we have a==0 and b==1 and n>0. Actually we need to stop when the pair (current a, next b) equals (0,1) and we have advanced to the next index? Standard approach: Fibonacci modulo m periodic with period π(m) such that F_π(m) ≡ 0 mod m and F_{π(m)+1} ≡ 1 mod m. So we can simulate until we encounter (0,1) as consecutive terms. The period length is the index when we see (0,1) again. Since we start with (F_0,F_1)=(0,1), the period is the smallest positive integer k such that (F_k, F_{k+1}) = (0,1). So we can simulate until we see a=0 and b=1 at some step after the initial. Typically we start with n=0: a=0, b=1. Then we iterate: for n=1: we compute next? Actually we need to be careful: The recurrence: F_0=0, F_1=1. For n>=2, F_n = F_{n-1}+F_{n-2} mod m. So in simulation, we can have variables prev = 0, cur = 1, for idx=0,1,... . At idx=0: (prev,cur)=(0,1). At each step, compute next = (prev+cur)%m; then shift: prev=cur; cur=next; increment idx. After moving to idx=1: now we have prev=1, cur=1. At idx=2: prev=1, cur=2, etc. The period is when (prev,cur) becomes (0,1) again. That is after the iteration? The condition to stop: after we have updated to a new state, if prev==0 and cur==1, then the number of steps taken is the period. Usually we start with (a0,b0)=(0,1). Then after k steps we have (a_k, a_{k+1}) = (0,1). So we can simulate until (prev,cur)==(0,1) and we are not at the start (i.e., index>0). Since the initial state is at index 0, we need to skip that.
Given that the period is ≤2028, we can simulate up to say 10000 to be safe, but 2028 is small.
But wait: There's a nuance: The bound dividing 2(p+1) is for prime p. However, is 1013 definitely prime? Let's verify: 1013 is indeed a prime number. Known list: 1013 is prime. Double-check: sqrt(1013) ≈ 31.8, test primes up to 31: 2,3,5,7,11,13,17,19,23,29,31. 1013 mod 7 = 1013-7144=1013-1008=5; mod 11: 1192=1012 remainder 1; mod 13: 1377=1001 remainder 12; mod 17: 1759=1003 remainder 10; mod 19: 1953=1007 remainder 6; mod 23: 2344=1012 remainder 1; mod 29: 2934=986 remainder 27; mod 31: 3132=992 remainder 21. So prime.
Thus π(1013) is a divisor of 2028. That is manageable.
But wait: There's a known result: For primes p where 5 is a quadratic residue, π(p) divides p-1; else divides 2(p+1). Here 5 is not a quadratic residue mod 1013 because 1013 mod5=3 and Legendre symbol (5/1013) = (1013 mod5) because of quadratic reciprocity? Actually (5/p) = 1 if p ≡ ±1 mod5, -1 if p ≡ ±2 mod5. So for p=1013 ≡ 3 mod5, (5/1013) = -1, so 5 is a quadratic non-residue. So indeed π(p) divides 2(p+1). Good.
But is it guaranteed that the period exactly divides 2(p+1), not necessarily that it is equal? It could be a proper divisor. For p=13, 2(p+1)=28 and period is 28; for p=7, period is 16, which is 2*8=16; for p=17, period is 36? 2(p+1)=36, so maybe 36. For p=19 (19 mod5=4 which is -1 mod5? Actually 19 mod5=4 = -1, so p ≡ ±1 mod5, then period divides p-1=18. Known Pisano period for 19 is 18? I think it's 18. So that fits. So the bound is tight.
Thus for p=1013, π(p) could be any divisor of 2028. To be safe, we can compute the actual period by simulation until we hit (0,1). Since 2028 is small, we can easily do that.
Now the main challenge: f is up to 1012, which is less than 1013. But the input may be up to 1012? Actually the problem statement: "0 ≤ f < 1013". So f can be from 0 to 1012 inclusive. So there are 1013 possible values.
We need to output the first occurrence index (0-indexed) of f, or -1 if never occurs. Since we can compute the whole period (up to 2028) and record first occurrence for each residue, we can answer in O(period) time. Period is at most 2028, but careful: it might be exactly 2028, maybe larger? Could it be larger than 2028? The theorem states it divides 2(p+1). So maximum is 2(p+1) = 2028. So indeed <=2028. So we can safely simulate up to 2028 or until we see (0,1) again.
But we need to be careful: The period might be exactly 2028? Possibly. Let's test small p that are ±2 mod5: p=3 -> period 8 = 24=8; p=7 ->16=28; p=13 ->28=214; p=17? Let's check: 17 mod5=2, period? I think it's 36? Actually I recall that π(17)=36, which is 218=36, p+1=18, yes. p=23? 23 mod5=3, period? Possibly 48? 2(p+1)=48; known π(23)=48? Actually I think π(23)=48. So pattern: often period = 2(p+1) for many primes where 5 is non-residue. But not always; e.g., p=47? 47 mod5=2, 2(p+1)=96; π(47) is maybe 32? Not sure. But it could be a divisor less than 2(p+1). So we must compute.
Thus algorithm:
- Read f.
- Set m = 1013.
- Simulate Fibonacci modulo m: start with a = 0, b = 1.
- We'll store an array first_occurrence of size m, initialized to -1.
- For index n from 0 upwards:
- If first_occurrence[a] == -1, set it to n.
- If a == 0 and b == 1 and n > 0: break (we've completed one full period; but we still need to consider the occurrence at index 0? Actually at n=0 we have a=0,b=1. At some later index k, after advancing, we will have (a,b) = (0,1) again. At that moment, we have just set a and b for the next term? Let's decide:
- At start: n=0, a = F0 = 0, b = F1 = 1.
- Then for n=0, we record a.
- Then compute next = (a+b) % m, set a = b, b = next, n += 1. Now n=1, a = F1 = 1, b = F2 = 1.
- Continue.
- We want to stop when we have returned to the state (F_n, F_{n+1}) = (0,1). That occurs at some n = period. At that n, a = 0, b = 1. But note that at n=0 we already had that state. So we break when (a==0 and b==1) and n != 0. But we must also record the occurrence of a at that n before breaking? If we break immediately, we might miss recording the occurrence of a=0 at index n (which is the same as index 0). But first occurrence of 0 is already recorded as index 0, so no need to record again. However, we need to ensure we've recorded all residues that appear in one full period. Since the period is the smallest positive integer k such that (F_k, F_{k+1}) = (0,1). Then the sequence from 0 to k-1 is one full period. At index k, we have a = F_k = 0, which is same as at index 0. So if we break when we see (a,b)=(0,1) and n>0, we have just processed index n = k, where a=0. But the period is k, and the terms indices 0...k-1 are the unique block. Index k is the start of the next period, duplicate of index 0. So we should not include index k in our search for first occurrences because they are not first (they are repeats). So we can break before recording index k? Actually if we record index k, we would set first_occurrence[0] maybe to k if not set, but it's already set to 0, so no harm. But we want to stop at the point where we have covered the first period. It is simpler to simulate until we see (a,b) = (0,1) after having processed at least one step. But we need to ensure we have recorded all indices from 0 up to k-1. When we get to index n = k, we have already recorded the a value for that index (0). But we haven't yet moved to index k+1. Since we break at the start of the next period, we have recorded indices 0..k. Index k is duplicate of index 0, but we already recorded index 0. So it's okay. Alternatively, we could break after we compute next and before incrementing n? Let's think carefully.
Standard method: Initialize: a = 0, b = 1, for n = 0,1,2,...:
- Record a if not recorded.
- If a == 0 and b == 1 and n > 0: break // because we have returned to initial state, so we've completed a full period and are at the start of the next; the next terms will repeat.
- Compute next = (a + b) % m
- Set a = b, b = next
- n++
But note: At n=0, a=0,b=1, we check condition (n>0 false) so continue. Then we compute next = 1, set a=1,b=1, n becomes 1 (by increment). Then at n=1, we record a=1 if not recorded, check if a==0 and b==1? No. Compute next=2, a=1,b=2, n=2, etc. Eventually when we hit the state where after updating we have a=0,b=1 at some index n, we will check the condition at the start of the loop for that n. Suppose at some step we have a=0,b=1 with n>0, then we break before recording a? Actually we record a at the start of loop, then check break. So if a=0,b=1 with n>0, we will record a (0) again (but it's already recorded). Then break. So we would have recorded index n, which is a duplicate of 0. But that's fine.
Now after break, we have recorded first occurrences for all indices that occurred during the first period, plus possibly the duplicate at index period. But if a residue appears first at index period (which is 0 only), it's not a new occurrence. So no problem.
Alternatively, we could break right after detecting the pair before recording, but then we might have not recorded some residue that appears only at index period? But only residue 0 appears at index period, and 0 already recorded. So it's safe.
Thus we can simulate until we detect (a,b) = (0,1) with n>0.
Given that period is at most 2028, the loop will run at most 2029 iterations (including the final detection). That's trivial.
Then we answer: print first_occurrence[f] if not -1, else -1.
But we must be careful about the range: f < 1013, but the period could be as low as, say, a divisor. So first_occurrence array of size 1013 is fine.
Edge Cases: f=0 -> answer should be 0, since first occurrence of 0 is at index 0. (Check: Fibonacci: F0=0). So output 0. f=1 -> first occurrence at index 1? Actually list: index0:0, index1:1, index2:1. So first occurrence of 1 is at index 1. So answer 1. So our algorithm will record index0 for 0, index1 for 1 (since first time we see 1 is at index1, index2 will see 1 again but already recorded). So ok.
Now we need to confirm that for m=1013, the period indeed does not exceed maybe 2028. But the theorem says divides 2(p+1). But is that always true for all primes? I recall that the Pisano period for prime p, denoted π(p), satisfies π(p) | p - 1 if p ≡ ±1 mod 5, and π(p) | 2(p+1) if p ≡ ±2 mod 5. This is a known result from the theory of Lucas sequences. Yes, it's correct. So for p=1013, we are safe.
But wait: The problem states "list of all Fibonacci numbers modulo 1013". So modulo is 1013. But 1013 might not be prime? I'm pretty sure it is prime. However, just to be rigorous, we could also compute the Pisano period by simulation until we see (0,1) again, but we need to know an upper bound to ensure we stop. Without a known bound, we might need to simulate many iterations if period is huge (could be up to 1013*...?). But given that m=1013 is small and typical Pisano periods can be O(m) actually for composite numbers it can be huge. But if m is not prime, the period could be as large as something like m * something. For m=1013, if it were composite, the period could be up to 6m? Actually maximum Pisano period for m is at most 6m. But for general m, it's not too high, but still could be like 61013=6078. That's still manageable. But if m were large like 10^9, that would be problematic. Here m=1013 is small. So we could just simulate until we hit (0,1) again, without any theoretical bound, because the period is bounded by something like 1013 * something, which is small. Actually known: Pisano period for m is at most 6m, and for m ≤ 10000, the period is at most 30000 maybe. So we can simulate until we find (0,1) again, with a loop up to, say, 1000000 to be safe. But that is still trivial. However, we should guarantee termination: The sequence of pairs (a,b) modulo m has at most m^2 possible states. Since we start with (0,1) and recurrence is reversible (since determinant -1?), it must eventually repeat. The maximum period length is at most m^2. For m=1013, m^2 = about 1,026,169, which is large but still feasible? Simulating up to 1 million steps might be okay in C++ but we need to be careful about time limits? The problem likely expects a more clever solution, but m is only 1013, and period might be at most 2028 if prime, but if composite, it might be bigger. But m=1013 is prime, we can be confident. However, maybe the problem's modulo 1013 is chosen exactly because it's prime and the period is small, so it's easy. So we can implement simulation.
But we also need to note: The problem says "Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier." That's a typical Codeforces note. So the input f is an integer less than 1013, not necessarily 64-bit; it's small. But it's okay.
Thus answer is straightforward.
But let's test with given examples: Input 13: We need to find first n such that F_n mod 1013 = 13. Since 13 < 1013, it appears at n=7 (F_7=13). Indeed output 7. That matches.
Input 377: 377 is F_14? Actually F_14=377. So n=14. Output 14.
But wait: Is 377 mod 1013 = 377, so indeed first occurrence at n=14, because F_14=377. So matches.
Now test some other values: f=0 -> 0. f=1 -> 1. f=2 -> 3? Actually F_3=2, yes first occurrence at 3. f=3 -> 4. f=5 -> 5. f=8 -> 6. f=13 ->7. f=21 -> 8? Actually F_8=21, yes. So pattern: For f that are Fibonacci numbers less than 1013, the first occurrence is the usual index. But for other residues, we need to compute.
But also note that for f values that are not typical Fibonacci numbers, they may appear later due to mod. For example, mod 13, f=4? Check: In the list for mod13, 4 does not appear; output -1. So we must handle.
So our algorithm will work.
But we must be cautious: The period might be smaller than our simulation break condition? Actually we will break when we see (0,1) again. That ensures we've covered exactly one full period. Since the period is small, we can compute.
Implementation details:
- Use int for modulus operations (since m=1013, fits in int).
- Use vector first(1013, -1).
- Initialize a=0, b=1, idx=0.
- Loop while true: if first[a] == -1: first[a] = idx. if (a==0 && b==1 && idx != 0) break; // compute next int c = (a + b) % 1013; a = b; b = c; idx++; // Note: after updating, we have advanced to next index.
- After loop, answer = first[f].
But check: At the start, idx=0. We record a (0). Check condition: a==0 && b==1 && idx!=0 false (idx=0). Then compute c = (0+1)%1013=1; a=1; b=1; idx=1. Next iteration: idx=1, a=1,b=1. Record a=1 if first[1]==-1. Check condition: a==0&&b==1? false. Compute c=2; a=1; b=2; idx=2. Continue. Suppose period = k. At index k, after updating we get a=0,b=1. At the start of loop when idx = k, a=0,b=1. Since idx !=0, we will break after recording a=0 again (already recorded). So we break and exit. That's fine.
One nuance: What if the period is 0? Not possible.
Now check if we need to handle f >= 1013? Input says 0 ≤ f < 1013. So it's fine.
Now test with f=4 mod 1013? Let's compute if 4 appears? Possibly yes? Not sure. But algorithm will determine.
Now confirm the bound: For p=1013, the period might be as small as, say, 1? No, not 1 because F_1=1 not 0. So it's at least 2? Actually (0,1) repeats at period k > 0. So k > 0.
We can also compute the period explicitly: We can simulate to find k. But we don't need to output it.
Potential pitfalls: Since we are using modulo 1013, but Fibonacci numbers can be huge; we only need modulo. Use int.
Now consider if there is any off-by-one: The problem asks: "print a single number — the number of the first occurrence of the given number in John's list. If this number doesn't occur in John's list, print -1." So we need to output index.
Now test with sample:
Simulate for f=13: we should get 7.
Our simulation: we compute and record indices. Let's simulate quickly:
idx:0 a=0 -> record0. update: a=1,b=1, idx=1 idx=1 a=1 -> record1 (first[1]=1) update: a=1,b=2, idx=2 idx=2 a=1 -> already recorded. update: a=2,b=3, idx=3 idx=3 a=2 -> record2 at 3. update: a=3,b=5, idx=4 idx=4 a=3 -> record3 at4. update: a=5,b=8, idx=5 idx=5 a=5 -> record5 at5. update: a=8,b=13, idx=6 idx=6 a=8 -> record8 at6. update: a=13,b=21, idx=7 idx=7 a=13 -> record13 at7. So first[13]=7. Works.
Now for f=377: 377 appears at idx? Let's simulate: continue from above:
After idx=7, update a=21,b=34 idx=8 idx=8 a=21 -> record21 at8? Actually F8=21, yes. ... We eventually get F14=377 at idx14. So first[377]=14.
Now what about f=1012? Might not appear. We'll compute.
Thus algorithm is correct.
But we need to be absolutely certain that the period is indeed <= 2028, because otherwise simulation might be long if period is larger (like up to 1 million). However, we can also accept simulation until we see (0,1) again, even if it's up to 1e6, it's still fine for time. But we need to confirm the maximum possible period for modulus 1013. Since 1013 is prime, the period divides 2(p+1)=2028. So maximum is 2028. So simulation of at most 2029 iterations is trivial.
But what if 1013 is not prime? Let's double-check: 1013 is indeed prime. It's a known prime. So fine.
But just for safety, we can implement with no assumption: simulate until we see (0,1) again or we've done maybe 2000000 steps to avoid infinite loop. But given constraints, it's okay.
Now edge: f=0: output 0. f=1: output 1. f=1012? Might be -1.
Now we should verify that for m=1013, the period exactly equals 2028? Let's test quickly by computing Legendre symbol: (5/1013) = -1, so the order of the matrix in GL(2, p) divides p^2-1 = 1026168, but the bound 2(p+1) is a divisor of that? Actually the order of the matrix is either divisor of p-1 or 2(p+1) depending on if 5 is quadratic residue? Let's recall: For prime p ≠ 5, the Fibonacci period modulo p is equal to the order of the matrix M = [[1,1],[1,0]] in GL(2,p). The characteristic polynomial is λ^2 - λ - 1 = 0. Its eigenvalues are α, β = (1 ± √5)/2. In GF(p), if 5 is a square, then α, β ∈ GF(p), and M is diagonalizable, and its order divides p-1. If 5 is not a square, then α, β ∈ GF(p^2) and are Galois conjugates; then the order of M divides p+1? Actually I think the order divides p-1 if 5 is quadratic residue; if not, the order divides 2(p+1)? Wait, recall: For Lucas sequences, the period of the Fibonacci numbers modulo a prime p (the so-called "Pisano period") is the order of the element in the multiplicative group of GF(p^2). More precisely, define τ = α/β? Hmm. Actually known: For p odd prime, the entry point (the index of the first zero modulo p) divides p - (5/p). And the period divides something like entry point * something? I'm mixing.
Better to recall known theorem: For prime p ≠ 2,5, the Pisano period π(p) divides p−1 if p ≡ ±1 mod 10? Actually I recall: For p ≡ ±1 mod 5, π(p) | p−1; for p ≡ ±2 mod 5, π(p) | 2(p+1). Yes that's a standard result. So I'll trust that.
Thus maximum 2028.
But maybe there is a nuance: The period might be a divisor of 2(p+1), but could also be a divisor of (p+1) in some cases? Actually some sources say for p ≡ ±2 mod 5, π(p) divides 2(p+1) but could also divide (p+1)? For example, p=3: 2(p+1)=8, π(3)=8, not divisor of 4. p=7: 16. p=13:28. p=23:48? For p=23, π(23) = 48 (I think). p=47? I'd like to check: 47 mod 5 = 2, 2(p+1)=96. I'm not sure if π(47) is 32 or 96? I could compute quickly mentally? But it doesn't matter; we can compute.
Thus simulation is easy.
Now implementation:
- Read integer f.
- Set mod = 1013.
- vector first(mod, -1).
- int a=0, b=1, idx=0.
- while(true) { if (first[a] == -1) first[a]=idx; if (a==0 && b==1 && idx != 0) break; int c = (a+b) % mod; a = b; b = c; idx++; }
- output first[f] (if -1 print -1).
But note: The sequence after the break condition we may have not recorded some residues that only appear after the period? Since the sequence repeats, any residue that appears at index >= period is a repeat of some earlier index. So first occurrences are only within indices 0..period-1. Our loop records indices up to period inclusive, but the period index (duplicate of 0) may record 0 again. But any other residue that appears for the first time at index period? Only 0. So that's fine.
Thus answer.
Now confirm that we handle f up to 1012 correctly.
Now test with some values manually using code? Not necessary but we can reason.
Now consider if f=1012: Our simulation will go through all residues that appear. At the end, if first[1012] remains -1, output -1.
Now potential issue: The period might be as small as e.g., 1? But impossible. So loop will exit.
Now double-check: At idx = 0, we record a=0. Condition check: a==0&&b==1&& idx!=0 false, compute, idx becomes 1. Then when we eventually hit period k, at idx=k, a=0,b=1, idx!=0 true, so we break. So we break after recording a=0. That means we have processed indices 0 through k inclusive. That includes index k, which is a duplicate of index 0. But it's okay.
However, there is a subtlety: The period is defined as smallest positive integer such that F_k ≡ 0 mod m and F_{k+1} ≡ 1 mod m. In our simulation, after we have computed a and b to represent (F_idx, F_{idx+1}), we have at idx=0: (0,1). When we update, we get to idx=1: (F1, F2) = (1,1). The condition for period is (F_idx, F_{idx+1}) = (0,1). So we need to have idx = k such that a=0 and b=1. That is correct.
Now what about the possibility that the period is 0? No.
Thus algorithm done.
Now we can also compute the period explicitly: after break, idx is the period? Let's see: At break, we are at index = k (where (F_k, F_{k+1}) = (0,1)). So idx = k. But note that we incremented idx after each update. So after we set a,b for index idx, we have that state. So at break, idx equals k. So period = idx.
Now if we wanted to be more efficient we could break before recording duplicate 0, but it's okay.
Now memory: first array size 1013.
Now answer.
Now we should consider if f can be >= 1013? Input says 0 ≤ f < 1013, so no.
Now output is an integer, maybe large? The index could be up to period -1 <= 2027. So it's small.
But wait: The index for first occurrence might be larger than the period? No, first occurrence must be within the first period, because if it appears later it would have appeared earlier as the sequence repeats.
Thus answer is <= 2027.
But is it possible that the first occurrence is after the period because the period starts after some pre-period? For Fibonacci modulo m, it is purely periodic from the start because the recurrence is reversible? Actually linear recurrence with constant coefficients and initial conditions can have a pre-period if the modulus is not coprime to the determinant? For Fibonacci, the recurrence is F_{n+2} = F_{n+1} + F_n. Mod m, since we have F_0=0, F_1=1, and the recurrence is linear, the sequence is purely periodic (no pre-period) because it's defined by a linear recurrence that is invertible? Actually the recurrence is not invertible? Given F_n and F_{n+1}, we can compute F_{n-1} = F_{n+1} - F_n. So it's reversible modulo m? The backward recurrence requires subtraction, but if we consider the state (F_n, F_{n+1}), the transition matrix M = [[0,1],[1,1]] is invertible mod m because its determinant is -1 mod m, which is invertible if gcd(-1,m)=1, which is always true. So the state transition is invertible, so the sequence of states is purely periodic from the start; i.e., it returns to the initial state after some period, and all subsequent states repeat. So there is no pre-period; it's a cycle. So first occurrence must be in the first period.
Thus algorithm correct.
Now implementation details: We'll use int for idx; max < 10000. So int fine.
Now complexity: O(period) which is <=2028.
Now we should think about any tricky issues: The problem statement: "John Doe has a list of all Fibonacci numbers modulo 1013. This list is infinite, it starts with numbers 0 and 1. Each number in the list, apart from the first two, is a sum of previous two modulo 1013." So it's exactly as we said.
Now the note: "Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier." This is just a standard Codeforces note for 64-bit integers. But here our integers are small, so we can just use int.
But f is given as an integer maybe up to 1012, but could be read as int.
Now code: We'll implement in C++.
Pseudo:
#include <bits/stdc++.h> using namespace std; int main() { const int MOD = 1013; int f; cin >> f; vector first(MOD, -1); int a = 0, b = 1; int idx = 0; while (true) { if (first[a] == -1) first[a] = idx; if (a == 0 && b == 1 && idx != 0) break; int c = (a + b) % MOD; a = b; b = c; ++idx; } cout << first[f] << endl; return 0; }
But is there any risk that we loop forever because the condition (a==0 && b==1) never occurs? Since the state space is finite, it must occur eventually. But could there be a situation where the initial state (0,1) is never revisited? Because the state space is finite and the mapping is a permutation (since matrix is invertible), the states form a cycle. Starting from (0,1), we must eventually return to it because the permutation is finite. So yes, it must occur.
Thus algorithm terminates.
Now test with sample:
Input 13 -> output 7.
Run mental: We'll compute first[13] = 7.
Now for f=377 -> output 14. Should get.
Now verify for f=1012? We need to compute if 1012 appears. Not sure but our code will produce -1 if not recorded.
Now we could also compute the period and confirm that all residues that appear are recorded.
Edge: What if f = 1013? Input range is <1013, so not.
Now I think it's correct.
But before finalizing, I want to double-check the period for 1013. According to known theorems, the Pisano period for prime p where 5 is a quadratic non-residue divides 2(p+1). For p=1013, 2(p+1)=2028. So period is a divisor of 2028. So it is at most 2028. But we can confirm by computing quickly with code mental? Not necessary.
Now there is also a known concept: "rank of apparition" of prime p, denoted r(p), which is the smallest n>0 such that p divides F_n. For p=1013, the rank of apparition divides p - (5/p) = p+1 = 1014 because (5/p) = -1. Actually known: For prime p, the entry point (the smallest positive n such that p divides F_n) divides p - (5/p). So r(p) divides p+1 = 1014. Then the Pisano period π(p) equals r(p) * something: Usually π(p) = r(p) * t where t is the order of something. In fact, for prime p, π(p) = r(p) * k, where k is a divisor of the multiplicative order of something. But there is known: π(p) divides p-1 if p ≡ ±1 mod5, and π(p) divides 2(p+1) if p ≡ ±2 mod5. So indeed.
Thus maximum 2028.
Now but wait, the rank of apparition for p is the smallest n such that F_n ≡ 0 mod p. That is the index of first 0 (excluding 0 at index 0? Actually F_0=0, so trivial zero; but we consider n>0. For the Fibonacci sequence modulo p, zero appears at index 0 and then again at some positive index, which is the rank. That index divides p-1 or p+1 accordingly. So for p=1013, r(p) divides p+1=1014. So the first positive index where we see 0 again divides 1014. For p=13, r(13) = 7? Actually F_7=13? Wait F_7=13, so 13 divides F_7? 13 divides 13, so r(13)=7. And 7 divides 14? p+1=14, 7 divides 14. Yes. So r(p) divides p+1. And period π(p) for p=13 is 28 = 214 = 2(p+1). So π(p) = 2 * r(p) if something? For p=13, r=7, π=28 =47? Actually 47=28, not 27. For p=7, r(7)=? F_? 7 divides F_? F_8=21? Actually 7 divides 7? F_? F_4=3, F_5=5, F_6=8, F_7=13, F_8=21, 7 divides 21? Yes, so r(7)=8? Wait index 8? Actually F_8=21, so 7 divides 21 => r(7)=8. But check: F_0=0 trivial, r is smallest positive n with p | F_n. So for 7, does F_? F_4=3, F_5=5, F_6=8, F_7=13, F_8=21, 21 mod7=0, so r=8. p+1=8, so r divides p+1 (8). And π(7)=16 = 2 * r? 28=16. For p=3, r(3)=4? Actually F_4=3 mod3=0, so r=4. p+1=4, so r divides 4. And π(3)=8 = 2r. For p=2? Not prime maybe, but r(2)=3? Actually F_3=2 mod2=0, so r=3, p+1=3, π(2)=3? Wait mod2: sequence: 0,1,1,0,1,1,0,... period=3. So π(2)=3, which equals r? Not 2r. For p=5 special case. So for primes p ≡ ±2 mod5, often π(p) = 2 * r(p) or maybe r(p) times something. But anyway, for p=1013, we can compute r(p) as the smallest positive index where we see 0 again. That divides 1014. And period might be 2 * r(p) or something. But since period divides 2028, it's fine.
Now I'd like to test a random prime like 37 (37 mod5=2, so p ≡ ±2 mod5). r(37) divides 38. Actually I think r(37)=19? Possibly. Then period maybe 76? Not sure. But still small.
Thus simulation with maximum 2028 steps is trivial.
Now potential issue: Our simulation might break before we have recorded all residues if the period is less than the loop break condition? Actually we break exactly when we have returned to (0,1). So we have processed the entire cycle. So we have recorded all residues that appear. So it's fine.
Now we must ensure we don't break prematurely if (0,1) appears but we haven't yet recorded all because we break at the start of the loop. That's okay.
Now the algorithm is done.
But before concluding, we should consider the possibility that f = 0 and the first occurrence is 0. Our code sets first[0]=0. Good.
Now we should also consider that there might be an occurrence of f at index beyond the period? No, because it repeats, so first occurrence is within first period.
Now we have to output -1 if not found.
Now is there any chance that the period is 0? Not possible.
Now implementation.
But wait: There's a nuance: The list is infinite and starts with numbers 0 and 1. So the 0th position is 0, 1st position is 1, 2nd is 1, etc. That matches our indexing.
Now is there any situation where f may appear only after the period because the period does not start at index 0? But we already argued it's purely periodic. More formally, because the recurrence is reversible (the transition matrix is invertible mod m), the state (F_n, F_{n+1}) must be periodic and the first repetition of a state leads to a cycle. Since we start with a unique state (0,1), the first time we revisit (0,1) we've completed a cycle. So indeed the sequence from 0 to period-1 is the first period. So first occurrence cannot be beyond period-1 because if it appeared later, it would also appear earlier due to the cycle? Actually not necessarily: Consider that the first repetition of a state might be a different state than (0,1) if the mapping is not a permutation? But it is a permutation. The state space is finite, and the function from state to next state is a permutation (bijection) because the matrix is invertible. So the trajectory from (0,1) must eventually repeat a state. Since it's a permutation, the only way to have a repeat is to return to the starting state? Actually in a permutation, cycles are disjoint. Starting from a state, you will follow a cycle and eventually return to the starting state because the orbit is a cycle. So the first repeat is the start state. So indeed we will only revisit (0,1) when we complete the cycle. So the sequence is purely periodic from start. So first occurrence is in [0, period-1].
Thus our approach is sound.
Now let's implement.
But we might also note that the modulus 1013 is prime, and we could use the known fact to compute the period analytically, but simulation is easier.
Now we need to write final answer in the required format.
Now test with sample.
Potential pitfalls: We need to ensure we treat f as integer. The input might be on one line.
Now we produce code.
But I should also test with a case where f is not present. For example, if we run for modulus 13 and f=4, we would get -1. For our modulus 1013, we can't manually test, but trust.
Now think about possible off-by-one: At index 0, we record 0. At idx=1, we record 1. At idx=2, we record 1 again but skip. So first[1]=1.
Now check that we correctly record first occurrence for numbers that appear only later. Example: For modulus 13, we expect first[10] = ? From earlier sequence: we saw 10 at index 19? Actually the sequence for mod13: 0:0 1:1 2:1 3:2 4:3 5:5 6:8 7:0 8:8 9:8 10:3? Actually need to list correctly: Let's generate properly:
F0=0 F1=1 F2=1 F3=2 F4=3 F5=5 F6=8 F7=13 mod13=0 F8=8 F9=8 F10= (8+0?) Wait careful: F7=0, F8=1? Actually need to compute: The recurrence: F_n = F_{n-1}+F_{n-2}. So F7 = F6+F5 = 8+5=13 ≡0. Then F8 = F7+F6 = 0+8=8. F9 = F8+F7 = 8+0=8. F10 = F9+F8 = 8+8=16 ≡3? 16 mod13 =3. Actually 16 mod13=3. So F10=3. F11 = F10+F9 = 3+8=11. F12 = F11+F10 = 11+3=14 ≡1. F13 = F12+F11 = 1+11=12. F14 = F13+F12 = 12+1=13 ≡0. F15 = F14+F13 = 0+12=12. F16 = F15+F14 = 12+0=12. F17 = F16+F15 = 12+12=24 ≡11 (24-13=11). F18 = F17+F16 = 11+12=23 ≡10. So first occurrence of 10 is at index 18. So our algorithm would detect that.
Now does the period for 13 end at index 28? At index 28 we have (F28,F29) = (0,1) again? Actually sequence of states: At idx=28: F28 = 0? I think the period is 28, so at index 28 we get F28=0, F29=1. So at idx=28, a=0,b=1, break. So we would have recorded index 18 for 10. So works.
Now for modulus 1013, similar.
Now one might wonder: Since the period divides 2028, but we might break earlier. But what if the period is exactly 2028, then we will loop 2029 times (including initial). That's fine.
Now complexity is trivial.
Thus final code.
But we must be careful about reading input: It says "The first line contains the single integer f". So only one integer.
Now we output a single number.
Now we can submit.
Wait: The problem might have a twist: The modulus 1013 is not prime? I'll double-check. 1013 divided by 3: 3337=1011, remainder 2. By 7: 7144=1008, remainder5. By 11: 1192=1012, remainder1. By 13:1377=1001, remainder12. By 17:1759=1003, remainder10. By 19:1953=1007, remainder6. By 23:2344=1012, remainder1. By 29:2934=986, remainder27. By 31:3132=992, remainder21. By 37:3727=999, remainder14. By 41:4124=984, remainder29. By 43:4323=989, remainder24. By 47:4721=987, remainder26. By 53:5319=1007, remainder6. No factor. So yes prime.
Now I think this is correct.
But one more nuance: The problem statement says "John Doe has a list of all Fibonacci numbers modulo 1013. This list is infinite, it starts with numbers 0 and 1. Each number in the list, apart from the first two, is a sum of previous two modulo 1013." It doesn't say that the list is periodic, but we know it is. However, it's fine.
Now edge case: f=1013? Not allowed.
Now write final solution.
But wait: Could there be a scenario where the period is less than the index where we first see f? No, because period includes all indices.
Now answer is ready.
Now code.
But I should also consider that the problem might be from Codeforces, and sometimes they expect you to compute using properties of Pisano period, but our solution is straightforward and within constraints.
Now test with sample:
Input 13 -> compute and output 7.
Input 377 -> output 14.
Now test with f=0 -> output 0.
Test with f=1 -> output 1.
Now we can implement.
Potential bug: The vector first of size 1013, but we might record values up to 1012. That's fine.
Now we also need to ensure that we don't break before recording a value that appears only at the index where we break? But only 0 appears at break. So if f=0, answer is 0, and break index also has 0 but we already recorded 0 at idx=0, so first[0] is 0. So break doesn't override.
Now what about f that is never recorded? Then first[f] remains -1, output -1.
Now what about f=1012? It might be recorded at some index, maybe 1012 appears? Not sure. But our code will output appropriate.
Thus final solution.
Now I'll produce final answer in C++.
But the problem might require handling large indices? The index might be up to 2027, which fits in int.
Now final code:
#include #include using namespace std;
int main() { const int MOD = 1013; int f; cin >> f; vector first(MOD, -1); int a = 0, b = 1; int idx = 0; while (true) { if (first[a] == -1) first[a] = idx; // check if we have returned to initial state (except idx 0) if (a == 0 && b == 1 && idx != 0) break; int c = (a + b) % MOD; a = b; b = c; idx++; } cout << first[f] << endl; return 0; }
Now verify: For f=13, output 7. For f=377, output 14. Works.
But what about f=1012? I can't verify but it's fine.
Now, could there be an issue: The input may be up to 1012, but we treat it as integer. Good.
Now final answer.
I'll also consider if there is any trick: The modulus is 1013, which is prime, but the period might be smaller, like maybe 1013? Not exactly. But the method is general.
Now we might also need to handle the case when f is 1013? Not allowed.
Thus solution complete.
Now produce final answer in response. ```cpp
#include #include
using namespace std;
const int MOD = 1013;
int main() { int f; cin >> f;
vector<int> first(MOD, -1); // first occurrence of each residue int a = 0, b = 1; // current (F_n, F_{n+1}) int idx = 0; // current index n while (true) { // record first appearance of current value if not seen before if (first[a] == -1) first[a] = idx; // stop when we are back at the initial pair, except for the start if (a == 0 && b == 1 && idx != 0) break; // advance one step int c = (a + b) % MOD; a = b; b = c; ++idx; } cout << first[f] << endl; return 0;}