poj3708(公式化简+大数进制装换+线性同余方程组)-白红宇

poj3708(公式化简+大数进制装换+线性同余方程组)

阅读量：6313 次

发布时间：2019-06-22

本文共 2264 字，大约阅读时间需要 7 分钟。

刚看到这个题目，有点被吓到，毕竟自己这么弱。

分析了很久，然后发现m，k都可以唯一的用d进制表示。也就是用一个ai，和很多个bi唯一构成。

这点就是解题的关键了。之后可以发现每次调用函数f(x),相当于a(ai),b(bi)了一下。这样根据置换的一定知识，一定会出现循环，而把循环的大小看成取模，把从m->k的看成余，于是可以建立一个线性同余方程。

直接用模板解决之。。

Recurrent Function

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1102		Accepted: 294

Description

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}$

Input

There are several test cases. The first line of each test case contains an integer

d (2≤

d≤100). The second line contains 2

d-1 integers:

₁, …,

a_d

_-1, followed by

₀, ...,

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.

Output

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".

Sample Input

211 047210 1100200-1

Sample Output

1NO

Hint

For the first sample case, we can see that

f(4)=7. And for the second one, the function is

i)=

////  main.cpp//  poj3708////  Created by 陈加寿 on 15/11/28.//  Copyright (c) 2015年 陈加寿. All rights reserved.//#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int a[110],b[110];char strm[110],strk[110];int m[110],k[110];int savem[1100],savek[1100];int cntm,cntk;void Tentod(int ten[],int len,int &cnt,int d,int save[]){    int tcnt=0;    while(ten[tcnt]==0) tcnt++;    cnt=0;    while(tcnt
           
            >=1; a=(a+a)%mod; } return sum;}//ax + by = gcd(a,b)//传入固定值a,b.放回 d=gcd(a,b), x , yvoid extendgcd(long long a,long long b,long long &d,long long &x,long long &y){ if(b==0){d=a;x=1;y=0;return;} extendgcd(b,a%b,d,y,x); y -= x*(a/b);}long long Multi_ModX(long long m[],long long r[],int n){ long long m0,r0; m0=m[0]; r0=r[0]; for(int i=1;i
            
             >d) { if(d==-1) break; for(int i=1;i
             
              >a[i]; for(int i=0;i
              
               >b[i]; scanf("%s",strm); scanf("%s",strk); int len = strlen(strm); for(int i=0;i

转载地址：http://xxxxa.baihongyu.com/

你可能感兴趣的文章