K尾相等数

 

K尾相等数

 

问题描述:

从键盘输入一个自然数K(K>1),若存在自然数M和N(M>N),使得K^M和K^N均大于或等于1000,且它们的末尾三位数相等,则称M和N是一对"K尾相等数".请编一程序,输出M+N值最小的K尾相等数.

 

方式一(按我的思路写的，很糟糕的程序)

 

/**
 * Copyright (c) 2011 Trusted Software and Mobile Computing(TSMC)
 * All rights reserved.
 * Author: Jarg Yee <[e-mail]>
 * http://jarg.iteye.com/
 */
import java.util.Scanner;
/*
 * 从键盘输入一个自然数K(K>1),若存在自然数M和N(M>N),使得K^M和K^N均大于或等于1000,且它们的末尾三位数相等,则称M和N是一对"K尾相等数".请编一程序,输出M+N值最小的K尾相等数.
 * K尾相等数
 * 
 * 耗时较高
 */
public class EqualNumber
{
	public static void main(String[] args) throws Exception
	{
		final int thresholdValue = 1000;		//临界值1000

		System.out.println("输入一个自然数K(K>1):");
		Scanner s = new Scanner(System.in);

		int index = 0;		//最小幂index,可以看作找K尾相等数循环下界

		long k = s.nextLong();			//要求输入大于或等于2的整数
		if(k >= thresholdValue)
		{
			index = 1;
			k = (int)k%thresholdValue;		//若k是很大的整数,则会出现乘积会出现上溢的情况
											// 在数论基础知识里曾证明过(M*N)%R = (M%R *N%R)%R
											// 这样做的原因是避免后面进行乘运算时数据溢出
		}

		int m, n;
		long mRemainder, nRemainder;	//m,n次幂对应的余数
		

		/*
			@TODO 找出满足大于或等于1000的最小幂index,可以看作找K尾相等数循环下界
			由于2的10次幂结果为1024,所以找出最小幂index的循环上界为10
		*/
		if(index == 0)
			for(int i=1; i<=10; i++)
			{
				if((long)(Math.pow(k, i)) >= thresholdValue)
				{
					index = i;
					break;
				}
			}
		

		n = index;				//e.g. k = 2且n = 10时, k^n = 1024 > 1000
		m = index;				//e.g. k = 2且m = 10时, k^m = 1024 > 1000

		boolean flag = true;	//控制变量:跳出整个循环
		while(flag)
		{
			++m;		//因为,m>n条件,所以一开始m+1
						//每次迭代对于当前m值,没有合适的n值,得到"K尾相等数",则+1

			mRemainder = remainder(k, m, thresholdValue);	//获取m
			for(n=index; n<m; ++n)
			{
				nRemainder = remainder(k, n, thresholdValue);

				/*
					@TODO 找到结果后跳出整个循环
				*/
				if(mRemainder == nRemainder)
				{
					flag = false;
					break;
				}
			}
		}
		System.out.println("m:\t" + m + "\tn:\t" + n);
		System.out.println(k + "尾相等数:\t" + (m + n));

	}

	/*
		@TODO 求得余数
		因为幂操作很可能超出int,甚至long的最大可表示值,
		所以每步都求其余数,代替求乘积再求余数的做法.
	*/
	public static int remainder(long k, int num, int thresholdValue)
	{
		int value = 1;
		for(int i=0; i<num; i++)
		{
			value = (int)(value*k);
			value = value%thresholdValue;		//求余数
		}
		return value;
	}

}

 

 

 

---------- 运行Java ----------

输入一个自然数K(K>1):

123454321

m: 26 n: 1

321尾相等数: 27

 

输出完成 (耗时 0 秒) - 正常终止

 

 

 

 

方式二(网上的思路翻译成的Java程序)

http://blog.csdn.net/virtualxmars/article/details/2422836

/**
 * Copyright (c) 2011 Trusted Software and Mobile Computing(TSMC)
 * All rights reserved.
 * Author: Jarg Yee <[e-mail]>
 * http://jarg.iteye.com/
 */
import java.util.Scanner;
/*
 * 从键盘输入一个自然数K(K>1),若存在自然数M和N(M>N),使得K^M和K^N均大于或等于1000,且它们的末尾三位数相等,则称M和N是一对"K尾相等数".请编一程序,输出M+N值最小的K尾相等数.
 * K尾相等数
 * 
 * 空间耗费较高
 * 
 * 抽屉原理:仔细思考后，我们可以注意到，任何数对1000求模只有1000种可能（0~999），所以我们将K^Power 中的Power从1（为什么不是0？因为K^0=1<1000，而我们不考虑小于1000的情况，题解第3点）到1001逐个求值，总有相等的两个数字。
 *
 */
public class KTail
{
	public static void main(String[] args) throws Exception
	{
		//由末尾三位数相等可知,余数会出现1000种情况
		//因此,设置一个余数数组,用来保存出现的各种余数
		//另外,最多1001次循环,必定能找到余数相同的值
		final int thresholdValue = 1000;			//临界值1000
		int[] remainder = new int[thresholdValue];

		//初始所有余数值为-1
		//将第一些得到对应余数值的幂值设为其余数数组对应值;下次取余数,获得对应的数组不为-1的话(出现余数重复的二个数),则表明找到另一个K尾相等数
		initRemainderArray(remainder);



		System.out.println("输入一个自然数K(K>1):");
		Scanner s = new Scanner(System.in);
		long k = s.nextLong();			//要求输入大于或等于2的整数


		int m=0, n=0;		//保存一对K尾相等数,其中m>n
		int value = 1;

		boolean flag = false;	//是否找到满足大于或等于1000的最小幂
		if(k >= thresholdValue)
		{
			flag = true;
			k = (int)k%thresholdValue;		//若k是很大的整数,则会出现乘积会出现上溢的情况
											// 在数论基础知识里曾证明过(M*N)%R = (M%R *N%R)%R
											// 这样做的原因是避免后面进行乘运算时数据溢出
		}

		for(int i=1; i<=thresholdValue; i++)	//迭代thresholdValue+1必定能找到K尾相等数
		{
			value = (int)(value * k);
			/*
				@TODO 从满足大于或等于1000的最小幂开始
			*/
			if(flag == false)
			{
				if(value >= 1000)
				{
					flag = true;
				}
				else
					continue;
			}

			value = value%thresholdValue;	//每次求余数,防止乘积越界的情况
			
			if(remainder[value] == -1)	//表示之前未设置过
			{
				remainder[value] = i;	//保存第一次得到此余数的幂值
			}
			else
			{
				m = i;
				n = remainder[value];
				break;
			}
		}
		System.out.println("m:\t" + m + "\tn:\t" + n);
		System.out.println(k + "尾相等数:\t" + (m + n));
	}

	/*
		@TODO 初始化余数数组
	*/
	public static void initRemainderArray(int[] remainder)
	{
		for(int i=0; i<remainder.length; i++)
		{
			remainder[i] = -1;
		}
	}
}

 

 

 

 

---------- 运行Java ----------

输入一个自然数K(K>1):

123454321

m: 26 n: 1

321尾相等数: 27

 

输出完成 (耗时 0 秒) - 正常终止