SGU 455 Sequence analysis(Cycle detection,floyd判圈算法)

题目链接: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,
  • SGU 455 Sequence analysis(Cycle detection,floyd判圈算法),

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 SGU 455 Sequence analysis(Cycle detection,floyd判圈算法) in programming, while SGU 455 Sequence analysis(Cycle detection,floyd判圈算法) 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 qq > 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 AB 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.

Input

The only line of input contains three signed 64-bit integers: AB and C (B > 0, C > 0).

Output

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");
}
上一篇:05_Tutorial 5: Relationships & Hyperlinked APIs 关系和超链接


下一篇:django rest framework 详解