{"problem":{"name":"D. Sequence analysis","description":{"content":"You are given a sequence of signed 64-bit integers defined as follows:  Let's call a sequence element xp _repeatable_ if it occurs later in the sequence — meaning that there exists such q, q > p, tha","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10050D"},"statements":[{"statement_type":"Markdown","content":"You are given a sequence of signed 64-bit integers defined as follows: \n\nLet's call a sequence element xp _repeatable_ if it occurs later in the sequence — meaning that there exists such q, q > p, that xq = xp. The _first repeatable_ element M of the sequence is such an element xm that xm is _repeatable_, and none of the xp where p < m are _repeatable_.\n\nGiven A, B and C, your task is to find the index of the second occurrence of the _first repeatable_ element M in the sequence if the index is less or equal to 2·107. Per definition, the first element of the sequence has index 0.\n\nThe only line of input contains three signed 64-bit integers: A, B and C (B > 0, C > 0).\n\nPrint a single integer  — the index of the second occurence of the _first repeatable_ member if it is less or equal to 2·107. Print  - 1 if the index is more than 2·107.\n\nIn the first sample test the sequence starts with the following numbers: 1, 3, 7, 6, 3, 7. The _first repeatable_ element is 3. The second occurence of 3 has index 4. \n\nIn the second sample test the sequence starts with the following numbers: 1, 2305843009213693951, -4611686018427387903, 6917529027641081855, 0, 0, 0. The _first repeatable_ element is 0. The second occurence of 0 has index 5. \n\nIn the third sample test the sequence starts with the following numbers: 1, -2, 4, -3, 1, -2, 4. The _first repeatable_ element is 1. The second occurence of 1 has index 4.\n\n## Input\n\nThe only line of input contains three signed 64-bit integers: A, B and C (B > 0, C > 0).\n\n## Output\n\nPrint a single integer  — the index of the second occurence of the _first repeatable_ member if it is less or equal to 2·107. Print  - 1 if the index is more than 2·107.\n\n[samples]\n\n## Note\n\nIn the first sample test the sequence starts with the following numbers: 1, 3, 7, 6, 3, 7. The _first repeatable_ element is 3. The second occurence of 3 has index 4. In the second sample test the sequence starts with the following numbers: 1, 2305843009213693951, -4611686018427387903, 6917529027641081855, 0, 0, 0. The _first repeatable_ element is 0. The second occurence of 0 has index 5. In the third sample test the sequence starts with the following numbers: 1, -2, 4, -3, 1, -2, 4. The _first repeatable_ element is 1. The second occurence of 1 has index 4.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ A, B, C \\in \\mathbb{Z} $ with $ B > 0 $, $ C > 0 $.  \nDefine the sequence $ (x_i)_{i=0}^{\\infty} $ by:  \n$$\nx_0 = A, \\quad x_{i} = (x_{i-1} \\cdot B + C) \\mod 2^{64} \\quad \\text{for } i \\geq 1.\n$$\n\nAn element $ x_p $ is *repeatable* if $ \\exists q > p $ such that $ x_q = x_p $.  \nThe *first repeatable* element $ M $ is $ x_m $, where $ m $ is the smallest index such that $ x_m $ is repeatable.\n\nLet $ j $ be the index of the *second occurrence* of $ M $, i.e., the smallest $ j > m $ such that $ x_j = x_m $.\n\n**Constraints**  \n- $ B > 0 $, $ C > 0 $  \n- All values are signed 64-bit integers (modulo $ 2^{64} $ arithmetic)  \n- We only consider $ j \\leq 2 \\cdot 10^7 $\n\n**Objective**  \nCompute $ j $ if $ j \\leq 2 \\cdot 10^7 $; otherwise output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10050D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}