我的欧拉工程之路――29

题目29：a的b次方（2≤a,b≤100）中共有多少个不同的数？

考虑?a^b?在 2?

2 ²=4,2 ³=8,2 ⁴=16,2 ⁵=32
3 ²=9,3 ³=27,3 ⁴=81,3 ⁵=243
4 ²=16,4 ³=64,4 ⁴=256,4 ⁵=1024
5 ²=25,5 ³=125,5 ⁴=625,5 ⁵=3125

如果将这些数字排序，并去除重复的，我们得到如下15个数字的序列：

4,8,9,16,25,27,32,64,81,125,243,256,625,1024,3125

a^b?在 2?

解答：欧拉工程有几道涉及大数运算的问题，例如，求2^1000，常常需要计算几百位的整数的加法，乘法等。于是，我自己实现了一个Num类，专门用来计算这种大数，可以满足欧拉工程的大数运算需求。

以下列出这个Num类的相关函数，并附上源码。此类目前可以完成2000位以下的加法、乘法、次方运算。如果需要增加支持的运算数范围，可以修改Num类中的arrayLen的值，其值乘以4便是支持的最大长度。

//空构造函数，初始化数值为0
public?Num()
//以整数初始化变量
public?Num(int?input)
//以字符串初始化
public?Num(String?str)
//清空变量，重置为0
public?void?clear()
//乘法，与b相乘，结果存储在调用者内
public?void?multiply(Num?b)
//打印此变量
public?void?print()
//返回存储整数的长度
public?int?len()
//复制a
public?void?clone(Num?a)
//加法，结果存储在调用者内
public?void?add(Num?b)
//设置数，以整数设置
public?void?setNum(int?input)
//设置数,用字符串设置
public?void?setNum(String?str)
//计算a^p，结果存储于a中
public?void?pow(int?p)
//返回所存储数的字符串
public?String?toString()

class?Num
{
	public?static?int?ArrayLen?=?500;
	private?int[]?num?=?new?int[ArrayLen];
	public?void?multiply(Num?b)
	{
		int?jinwei=0,l=(b.len()+3)/4;
		Num?result=new?Num(),temp=new?Num();
		for(int?i=0;i<l;i++)
		{
			temp.clear();
			for(int?j=0;j<=(this.len()+3)/4;j++)
			{
				int?t=(this.num[j]*b.num[i]+jinwei)%10000;
				jinwei=(this.num[j]*b.num[i]+jinwei)/10000;
				temp.num[i+j]=t;
			}
			result.add(temp);
		}
		this.clone(result);
	}
	public?void?clear()
	{
		for(int?i=0;i<ArrayLen;i++)
		{
			this.num[i]=0;
		}
	}
	//打印变量
	public?int?compare(Num?b)
	{
		int?result=0;
		for(int?i=ArrayLen-1;i>=0;i--)
		{
			if(this.num[i]!=b.num[i])
			{
				result=this.num[i]-b.num[i];
				break;
			}
			else?if(i==0)
			{
				result=0;
			}
		}
		return?result;
	}
	public?void?print()
	{
		int?i=ArrayLen-1;
		while(num[i]==0?&&?i>0)
			i--;
		System.out.print("num="+num[i]);
		while(--i>=0)
		{
			if(num[i]<10)
			{
				System.out.print("000");
				System.out.print(num[i]);
			}
			else?if(num[i]<100)
			{
				System.out.print("00");
				System.out.print(num[i]);
			}
			else?if(num[i]<1000)
			{
				System.out.print("0");
				System.out.print(num[i]);
			}
			else
			{
				System.out.print(num[i]);
			}
			
		}
		System.out.println("?");
	}	
	//返回此num对象存储的整数的长度
	public?int?len()
	{
		int?len=0;
		for(int?i=499;i>=0;i--)
		{
			if(num[i]!=0)
			{
				if(num[i]<10)
					len=i*4+1;
				else?if(num[i]<100)
					len=i*4+2;
				else?if(num[i]<1000)
					len=i*4+3;
				else
					len=i*4+4;
				break;
			}
			else?if(i==0)
			{
				len=1;
			}
		}
		return?len;
	}
	public?void?clone(Num?a)
	{
		for(int?i=0;i<ArrayLen;i++)
		{
			num[i]=a.num[i];
		}
	}
	public?void?add(Num?b)
	{
		for(int?i=0,jinwei=0;i<ArrayLen;i++)
		{
		
			int?t=(this.num[i]+b.num[i]+jinwei)%10000;
			jinwei=(this.num[i]+b.num[i]+jinwei)/10000;
			this.num[i]=t;
		}
	}
	public?Num(){}
	public?Num(int?input)
	{
		this.setNum(input);
	}
	public?Num(String?str)
	{
		this.setNum(str);
	}
	public?void?setNum(int?input)
	{
		int?i=0;
		this.clear();
		while(input>0)
		{
			this.num[i]=input%10000;
			input/=10000;
			i++;
		}
	}
	public?void?setNum(String?str)
	{
		this.clear();
		if(str.length()%4!=0)
		{
			int?i=4-str.length()%4;
			while(i-->0)
			{
				str="0".concat(str);
			}
		}
		int?len=str.length();
		for(int?i=0;i<len/4;i++)
		{
			this.num[i]=Integer.parseInt(str.substring(len-i*4-4,len-i*4));
		}
	}
	//运算a^p,存储在a中
	public?void?pow(int?p)
	{
		if(p==0)
		{
			this.clear();
			this.num[0]=1;
		}
		else?if(p>0)
		{
			Num?t=new?Num();
			t.clone(this);
			for(int?i=1;i<p;i++)
			{
				this.multiply(t);
			}
		}
	}
	public?String?toString()
	{
		String?s=new?String("num=");
		int?i=ArrayLen-1;
		while(num[i]==0?&&?i>0)
			i--;
		s+=num[i];
		while(--i>=0)
		{
			if(num[i]<10)
			{
				s+="000";
				s+=num[i];
			}
			else?if(num[i]<100)
			{
				s.concat("00");
				s+=num[i];
			}
			else?if(num[i]<1000)
			{
				s.concat("0");
				s+=num[i];
			}
			else
			{
				s+=num[i];
			}
		}
		return?s;
	}
}

实现这个类后非常简单就可以解决这个问题了，首先计算所有的数值，并将已计算的数值保存下来，以后获得的每个数值都跟之前的所有数进行比较，如果有重复的则不保存，反之，保存。以下是这部分的java代码。

public?class?Euler29
{
????public?static?void?main(String[]?args)
????{
????????Num[]?total=new?Num[9801];
????????for(int?i=0;i<9801;i++)
????????{
????????????total[i]=new?Num();
????????}
????????Num?t=new?Num(2),comp=new?Num();
????????for(int?i=2,pos=0;i<=100;i++)
????????{
????????????for(int?j=2;j<=100;j++)
????????????{
????????????????t.setNum(i);
????????????????t.pow(j);
????????????????int?k=0;
????????????????for(;k<pos;k++)
????????????????{
????????????????????if(t.compare(total[k])==0)
????????????????????{
????????????????????????break;
????????????????????}
????????????????}
????????????????if(k==pos)
????????????????{
????????????????????total[pos++].clone(t);
????????????????}
????????????}
????????}
????????for(int?i=0;i<9801;i++)
????????{
????????????if(total[i].compare(comp)!=0)
????????????{
????????????????System.out.print(i+1+"?");
????????????????total[i].print();
????????????}
????????????else
????????????{
????????????????break;
????????????}
????????}
????}
}

对于这道题，肯定有更简便的方法，但是我在做这道题的时候更加倾向于实现一个通用的大数运算的类，虽然这个类现在还不是很完善，比如，对于负数还不支持，另外，还未实现减法和除法，不过我会慢慢的加上这部分的。