1.根据题目要求是求出phi(m)的最小因子i是的10^i≡1 (mod m),
这里m=(9*L) /gcd(9*L,8) ),phi是欧拉函数;L<=2*10^9;
首先第一个问题就是有可能m求出来范围达到1.8*10^10这么大,
当枚举1~sqrt(m)范围内m的因子时,要检验10^i(mod m)是否是1,
在用二进制的方式求10^i(mod m)时,
我用代码如下:计算a^b mod n (bits[]用来存储b的二进制形式)
        int k;
	unsigned __int64 c,d;
	k=0;
	while(b)
	{
		bits[k++]=b&1;
		b>>=1;
	}
	k--;
	c=0;
	d=1;
	while(k>=0)
	{
		c<<=1;
		d=(d*d)%n;
		if(bits[k])
		{
			c++;
			d=(d*a)%n;
		}
		k--;
	}
	return d;
上面的代码用来计算10^i mod( m)时,由于m会大到1.8*10^10,所以若在某次循环时若d也接近1.8*10^10时,就会溢出unsigned __int64 了,这里就不知道怎么处理了,
不知道时候要用高精度,或者这种可以用浮点数如double的方式,保存d*d,来求模m?

• try this function~ (257) majia5 2008-10-27 22:56:26