3708：Recurrent Function

题目描述

Dr. Yao is involved in a secret research on the topic of the properties of recurrent function. Some of the functions in this research are in the following pattern:

$\begin{tabular} {ll} \textit{f}(\textit{j}) = \textit{a}$_j$ & for 1$\le$\textit{j}$<$\textit{d}, \\ \emph{f}(\emph{d}$\times$\emph{n}+\emph{j}) = d$\times$f(\textit{n})+\textit{b}$_j$ & for 0$\le$\textit{j}$<$\textit{d} and \textit{n}$\ge$1, \\ \end{tabular}$

in which set {a_i} = {1, 2, …, d-1} and {b_i} = {0, 1, …, d-1}.
We denote:

$\begin{tabular}{l}\emph{f}$_x$(\emph{m}) = \emph{f}(\emph{f}(\emph{f}($\cdots$\emph{f}(\emph{m})))) \quad\emph{x} times \\ \end{tabular}$

Yao's question is that, given two positive integer m and k, could you find a minimal non-negative integer x that

$\begin{tabular}{l}\emph{f}$_x$(\emph{m}) = \emph{k}\\ \end{tabular}$

输入解释

There are several test cases. The first line of each test case contains an integer d (2≤d≤100). The second line contains 2d-1 integers: a₁, …, a_d_-1, followed by b₀, ..., b_d_-1. The third line contains integer m (0<m≤10¹⁰⁰), and the forth line contains integer k (0<k≤10¹⁰⁰). The input file ends with integer -1.

输出解释

For each test case if it exists such an integer x, output the minimal one. We guarantee the answer is less than 2⁶³. Otherwise output a word "NO".

输入样例

输出样例

1
NO

提示

For the first sample case, we can see that f(4)=7. And for the second one, the function is f(i)=i.

该题目是Virtual Judge题目，来自北京大学POJ

题目来源 POJ Founder Monthly Contest – 2008.12.28, Yaojinyu

源链接： POJ-3708

最后修改于 2020-10-29T07:08:40+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
1000	65536