题目描述题目要求寻找最小的第一个因数记为NNN使得将NNN的最后一位数字移动到最前面后得到的新数等于NNN乘以第二个因数。数字使用给定的进制base\texttt{base}base第二个因数为一位数小于进制。输出NNN的位数。输入格式输入包含多行每行三个整数进制bbb2≤b≤10002 \le b \le 10002≤b≤1000、第一个因数的最低位数字mmm0≤mb0 \le m b0≤mb、第二个因数kkk1≤kb1 \le k b1≤kb。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每行输入输出一行一个整数表示最小的满足条件的第一个因数的位数。样例输入10 7 4 9 7 4 17 14 12输出6 2 4题目分析本题的核心是求解循环移位乘法问题。设NNN为ddd位数最低位为mmm将mmm移到最前面后得到新数N′NN′满足N′N×kN N \times kN′N×k。数学推导设NNN的十进制或bbb进制表示为Na1a2…adN a_1 a_2 \ldots a_dNa1​a2​…ad​其中adma_d mad​m。则N′ma1a2…ad−1N m a_1 a_2 \ldots a_{d-1}N′ma1​a2​…ad−1​。在bbb进制下N′m×bd−1(N−m)/bN m \times b^{d-1} (N - m) / bN′m×bd−1(N−m)/b。方程m×bd−1N−mbN×k m \times b^{d-1} \frac{N - m}{b} N \times km×bd−1bN−m​N×k两边乘以bbbm×bdN−mN×k×b m \times b^d N - m N \times k \times bm×bdN−mN×k×b整理m×bd−mN×(k×b−1) m \times b^d - m N \times (k \times b - 1)m×bd−mN×(k×b−1)Nm×(bd−1)k×b−1 N \frac{m \times (b^d - 1)}{k \times b - 1}Nk×b−1m×(bd−1)​由于NNN是整数且长度为ddd我们需要找到最小的ddd使得上式成立。算法从d1d 1d1开始递增计算m×(bd−1)mod (k×b−1)m \times (b^d - 1) \mod (k \times b - 1)m×(bd−1)mod(k×b−1)当余数为000时ddd即为答案。复杂度分析ddd最多为100010001000量级直接计算即可。代码实现// Multiplying by Rotation// UVa ID: 550// Verdict: Accepted// Submission Date: 2016-08-08// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intbase,first_factor,second_factor;while(cinbasefirst_factorsecond_factor){intn1,x,exponentbase;while(true){intrfirst_factor*(exponent-1)%(second_factor*base-1);if(r0)break;exponent(exponent*base)%(second_factor*base-1);n;}coutnendl;}return0;}