SGU 455 Sequence analysis(Cycle detection,floyd判輪アルゴリズム)
8271 ワード
タイトルリンク: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
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 "
"type in C++, "
"in Java and "
"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.
Input
The only line of input contains three signed 64-bit integers: A, B 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.第2の循環節の出現の位置を求めます.
考え方: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[2 i]である.
そこで,以下のコードを用いて,x[v]=x[2 v]を満たす最初のコードを見つけることができる.ν,明らかに[μ, μ + λ]v=kが存在するλ,このステップの複雑さはO(μ+λ).
任意i≧μ,x[i]=x[i+λ] = x[i + kλ],では同意はx[μ] = x[μ + λ] = x[μ + kλ] = x[μ + v].
上記のコードでは,両方の変数がx[v]に等しいx[v]を求めた.
ではx[μ] = x[μ + v]の事実.次のコードでループできますμ次,x[を求める.μ].
上記のコードはすでに求められているμx[μ].最後に、リサイクルさえすればλループ・セクションの長さを求めるには、次の手順に従います.
全時間複雑度O(μ+λ),空間複雑度はO(1)である.
本題に対して、出力μ+λできます.
本題の計算過程で溢れ出す可能性があることについては考えていませんが...みんなが気にしていないことに気づきました.私も気にしませんでした.
コード(312 MS):
View Code
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:
, where
modis 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.
Input
The only line of input contains three signed 64-bit integers: A, B 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.第2の循環節の出現の位置を求めます.
考え方: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[2 i]である.
そこで,以下のコードを用いて,x[v]=x[2 v]を満たす最初のコードを見つけることができる.ν,明らかに[μ, μ + λ]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)である.
本題に対して、出力μ+λできます.
本題の計算過程で溢れ出す可能性があることについては考えていませんが...みんなが気にしていないことに気づきました.私も気にしませんでした.
コード(312 MS):
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long LL;
4
5 const int MAXR = 2e6;
6
7 LL A, B, C;
8
9 LL next(LL x) {
10 return (A * x + x % B) % C;
11 }
12
13 int main() {
14 scanf("%I64d%I64d%I64d", &A, &B, &C);
15 LL x = next(1), y = next(x);
16 int v = 1;
17 while(v <= MAXR && x != y)
18 x = next(x), y = next(next(y)), v++;
19 if(v > MAXR) {
20 puts("-1");
21 return 0;
22 }
23
24 x = 1;
25 int mu = 0;
26 while(x != y)
27 x = next(x), y = next(y), mu++;
28
29 int lam = 1;
30 y = next(x);
31 while(mu + lam <= MAXR && x != y) y = next(y), lam++;
32
33 if(mu + lam <= MAXR) printf("%d
", mu + lam);
34 else puts("-1");
35 }View Code