NYOJ 212 K尾相等数

曾经终败给现在 2022-08-25 01:26 23阅读 0赞

## K尾相等数 ##

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 1

描述

输入一个自然数K（K>1）,如果存在自然数M和N（M>N），使得K^M和K^N均大于等于1000，且他们的末尾三位数相等，则称M和N是一对“K尾相等数”。下面请编程求出M+N最小的K尾相等数。

输入

第一行包含一个正整数T，T<10000，表示有T组数据；  
随后有N行，每行包括一个整数K（K<2\*10^10);

输出

对于输入的每个整数K，输出对应的M+N的最小值；

样例输入

1
    2

样例输出

120

**解题：**

无论拿到什么样的题目，把题目读懂是第一件必须做到的事情。然后是分析题目中的关键词语以及重点内容。

就上面的题目而言，我们必须注意到下面的要点：

1．四个要点量：K,M,N,1000，且K，M，N是自然数

2．K是M,N的底数，M,N是K的幂。

3．K^M 和 K^N都必须大于1000

4．K^M 和 K^N 末尾三位相等。

5．要输出的的是M+N的值

6．M>N（两个数不相等…人家不会让小聪明成功的，K^M当然和它自己相等）

**分析**：

1．上面的要点中，1，2，3，5,6都是辅助条件，关键是弄清楚第4点。末尾三位相等是什么意思？比如 123456 末尾三位是‘456’而 45678 末尾三位则是‘678’。显然（虽然我也不喜欢在书上看到这个字眼，但是这里确实是很显然……），这里指的是10进制数的末尾3位，如何取末尾3位的数字？很显然（ =.=! ）将这个数字对1000求模就可以了。

2．仔细思考后，我们可以注意到，任何数对1000求模只有1000种可能（0~999），所以我们将K^Power 中的Power从1（为什么不是0？因为K^0=1<1000，而我们不考虑小于1000的情况，题解第3点）到1001逐个求值，总有相等的两个数字。因为结果只有1000种可能，但是有1001次求值，哪怕前1000次所求结果都不一样，最后一次的值必然与前面1000种其中的一种相等（**相关知识：抽屉原理1**）。

**流程：**

根据上面的理解和分析，解决流程大致如下：

1．获得K的大小

2．逐个求K^Power (Power= 1,2,3…….1001)的结果并记录下来

3．若在记录的时候发现之前该值已经出现过，那么上次记录该值时的Power值和本次尝试记录时的Power值就分别是N和M了

4．输出M+N

**数据结构与设计技巧：**

1．其实这个程序不需要什么数据结构，但是有一个技巧还是得提到一下，K^Power末尾的三位数字只可能是0~999中的一种，而我们如何记录哪一种结果曾经出现过？最好的方法是使用一个一维数组，维数刚好是1000，分别记录0~999每种情况出现时Power的值。存取的时候可以利用末尾三位数本身的值作为该数组的索引来进行（**相关知识：重复计数2**）

2．其实我们也不需要逐个求K^Power的值，那样的运算效率太低了。考虑到 K^Power = K^(Power-1)，所以，利用这一性质，我们可以求出K^1的值，然后据此推出K^2到K^1001的结果就行了。

3. 当K或者Power比较大的时候它们相乘可能导致数据溢出，这就需要参考我的另一篇文章里的对大数进行求模运算的相关算法了，总之结果就是求M\*N%R,当M\*N可能溢出时，应该使用 ((M%R)\*(N%R))%R 来计算。

**程序代码：**

\#include <iostream>

\#include <memory>

using namespace std;

int Record\[1000\]; // 用以记录的一维数组

int KTail( int K )

memset( Record, 0, sizeof(Record) ); // 清除之前记录的内容

int Product = 1; // 记录逐次相乘的积，至于为什么从1开始，

// 请自行观察体会

bool bTakeRecord = false; // 需要一个标记，用以判断是否>=1000

if ( K>=1000 )

bTakeRecord = true;

K=K%1000; // 在数论基础知识里曾证明过(M\*N)%R = (M%R \*N%R)%R

\} // 这样做的原因是避免后面进行乘运算时数据溢出

for ( int Power = 1; Power<=1001; ++Power) // Power从1到1001

Product \*= K; // Product = (K^Power-1)%1000 \* K

if ( bTakeRecord || Product>=1000 ) // 必须符合题目的条件 K^Power>=1000

bTakeRecord = true; // 考虑到有可能之前是false，再赋值

Product = Product%1000; // 去结果的末尾三位！！！！

if ( Record\[Product\]==0 ) // 这个结果之前没出现过，记录结果出现时的幂值

Record\[Product\] = Power; // 记录之

else

return Power \+ Record\[Product\]; // 啊哈！出现过，那么返回我们的结果

return \-1; // 这行其实可以不写，因为不可能到这里，但是为了不让编译器提示编译警告

// 信息，还是加上吧。

int main()

int K;

while( (cin>>K).good() ) // 输入K值，并判断输入是否正常

cout<<KTail(K)<<endl; // 输出结果

return 0;

**测试数据：**

125

1000

1234

111111

1000003

123454321

**测试数据结果：**

102

以上思路转载自 [ http://blog.csdn.net/virtualxmars/article/details/2422836][http_blog.csdn.net_virtualxmars_article_details_2422836]

#include <stdio.h>
    #include <string.h>
    
    int record[1000];
    
    int KTail (int K)
    {
    	int i;
    	int product = 1;
    	int btakeecord = 0;
    	memset(record,0,sizeof(record));
    	if (K>=1000)
    	{
    		btakeecord = 1;
    		K = K % 1000;
    	}
    
    	for (i=1; i<=1001; ++i)
    	{
    		product *= K;
    		if (btakeecord || product>=1000)
    		{
    			btakeecord = 1;
    			product = product%1000;  
    
    			if (record[product] == 0)
    			{
    				record[product] = i;
    			}
    
    			else
    			{
    				return i + record[product];
    			}
    		}
    	}
    
    	return -1;
    }
    
    
    int main()
    {
    	int m;
    	scanf("%d",&m);
    	while (m--)
    	{
    		int K;
    		scanf("%d",&K);
    		printf("%d\n",KTail(K));
    	}
    	return 0;
    }

[http_blog.csdn.net_virtualxmars_article_details_2422836]: http://blog.csdn.net/virtualxmars/article/details/2422836