题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=455
Due to the slow 'mod' and 'div' operations with int64 type, all Delphi solutions for the problem 455 (Sequence analysis) run much slower than the same code written in C++ or Java. We do not guarantee that Delphi solution exists.
You are given a sequence of signed 64-bit integers defined as follows:
- x0 = 1,
- ,
where
mod
is a remainder operator. All arithmetic operations are evaluated without overflow checking. Use standard "remainder" operator for programming languages (it differs from the mathematical version; for example in programming, while in mathematics). Use "
long long
" type in C++, "
long
" in Java and "
int64
" in Delphi to store xi and all other values.
Let'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.
Given A, B and C, your task is to find the index of the second occurence of the first repeatable element M in the sequence if the index is less or equal to 2 · 106. Per definition, the first element of the sequence has index 0.
The only line of input contains three signed 64-bit integers: A, B and C (B > 0, C > 0).
Print a single integer — the index of the second occurence of the first repeatable member if it is less or equal to 2 · 106. Print -1 if the index is more than 2 · 106.
题目大意:给出x[0] = 1,还有A、B、C,有x[i+1] = (A * x[i] + x[i] % B) % C。求第二个循环节出现的位置。
思路:http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare (floyd判圈算法,龟兔算法?)
给一个初始值x[0],有一个函数x[i + 1] = f(x[i])。若x始终在有限集合中运算,那么这些x值会构成一个环。
在此题中,整数模一个C后,显然得到的值是有限的。
设第一个循环节从x[μ]开始,循环节长度为λ。
那么对任意i = kλ ≥ μ,一定会有x[kλ] = x[kλ + kλ],即x[i] = x[2i]。
于是我们可以用以下代码,找出满足x[v] = x[2v]的第一个ν,显然在[μ, μ + λ]间存在一个v = kλ,则此步复杂度为O(μ+λ)。
long long x = f(x0), y = f(f(x0));
int v = 1;
while(x != y)
x = f(x), y = f(f(y)), v++;
由于对任意i ≥ μ,有x[i] = x[i + λ] = x[i + kλ],那么同意有x[μ] = x[μ + λ] = x[μ + kλ] = x[μ + v]。
在上面的代码中,我们已经求得了x[v],其中两个变量都等于x[v]。
那么基于x[μ] = x[μ + v]的事实。我们可以用下面的代码,循环μ次,求出x[μ]。
x = x0;
int mu = 0;
while(x != y)
x = f(x), y = f(y), mu++;
上述代码已经求出μ与x[μ]。最后,只要再循环λ遍,即可求出循环节长度:
int lam = 1;
y = f(x);
while(x != y) y = f(y), lam++;
总时间复杂度为O(μ+λ),空间复杂度为O(1)。
对于本题,输出μ+λ即可。
至于本题的计算过程可能溢出的事情我没想……我发现大家都没管,我也不管了……
代码(312MS):
#include <bits/stdc++.h>
using namespace std;
typedef long long LL; const int MAXR = 2e6; LL A, B, C; LL next(LL x) {
return (A * x + x % B) % C;
} int main() {
scanf("%I64d%I64d%I64d", &A, &B, &C);
LL x = next(), y = next(x);
int v = ;
while(v <= MAXR && x != y)
x = next(x), y = next(next(y)), v++;
if(v > MAXR) {
puts("-1");
return ;
} x = ;
int mu = ;
while(x != y)
x = next(x), y = next(y), mu++; int lam = ;
y = next(x);
while(mu + lam <= MAXR && x != y) y = next(y), lam++; if(mu + lam <= MAXR) printf("%d\n", mu + lam);
else puts("-1");
}