> 用int处理速度极慢，对于(n>100000)等很长时间没结果
> 改用__int64可以在30ms左右计算出来。
> 请问两者区别在哪？
> 代码：
> #include <iostream>
> using namespace std;
> ////accepted code
> __int64 MultMod(__int64 base, __int64 pow, __int64 n)
> {
> 	__int64 result = 1;
> 	while(pow)
> 	{
> 		while(!(pow&1))
> 		{
> 			base = base*base % n;
> 			pow >>= 1;
> 		}
> 		result = result*base % n;
> 		pow --;
> 	}
> 	return result;
> }
> 
> bool RabbinMiller(__int64 n)
> {
> 	__int64 t = 0;
> 	__int64 M = n-1;
> 	__int64 v;
> 	__int64 a,i;
> 
> 	a = rand()%(n-1)+1;
> 	//cout <<"a="<<a<<endl;
> 
> 	while(!(M&1))
> 	{
> 		t++;
> 		M >>= 1;
> 	}
> 
> 	v = MultMod(a,M,n);
> 	
> 	if(v == 1)
> 		return true;
> 
> 	i = 1;
> 	while(v != n-1)
> 	{
> 		if(i == t)
> 		{
> 			return false;
> 		}
> 		v = MultMod(v,2,n);
> 		i++;
> 	}
> 	return true;
> }
> 
> bool NRabinMiller(__int64 n,int loop)
> {
> 	if(n < 2)
> 		return false;
> 	if(n == 2)
> 		return true;
> 	else if(!(n&1))
> 	{
> 		return false;
> 	}
> 	else
> 	{
> 		int i;
> 		for(i = 0; i < loop; ++i)
> 		{
> 			if(!RabbinMiller(n))
> 				return false;
> 		}
> 	}
> 	return true;
> 
> }
> /*
> //TLE when using int;
> int MultMod(int base, int pow, int n)
> {
> 	int result = 1;
> 	while(pow)
> 	{
> 		while(!(pow&1))
> 		{
> 			base = base*base % n;
> 			pow >>= 1;
> 		}
> 		result = result*base % n;
> 		pow --;
> 	}
> 	return result;
> }
> 
> bool RabbinMiller(int n)
> {
> 	int t = 0;
> 	int M = n-1;
> 	int v;
> 	int a,i;
> 
> 	a = rand()%(n-1)+1;
> 	//cout <<"a="<<a<<endl;
> 
> 	while(!(M&1))
> 	{
> 		t++;
> 		M >>= 1;
> 	}
> 
> 	v = MultMod(a,M,n);
> 	
> 	if(v == 1)
> 		return true;
> 
> 	i = 1;
> 	while(v != n-1)
> 	{
> 		if(i == t)
> 		{
> 			return false;
> 		}
> 		v = MultMod(v,2,n);
> 		i++;
> 	}
> 	return true;
> }
> 
> bool NRabinMiller(int n,int loop)
> {
> 	if(n < 2)
> 		return false;
> 	if(n == 2)
> 		return true;
> 	else if(!(n&1))
> 	{
> 		return false;
> 	}
> 	else
> 	{
> 		int i;
> 		for(i = 0; i < loop; ++i)
> 		{
> 			if(!RabbinMiller(n))
> 				return false;
> 		}
> 	}
> 	return true;
> 
> }
> */
> 
> int main()
> {
> 	int n;
> 	while(1)
> 	{
> 		scanf("%d",&n);
> 		if(n == 0)
> 			break;
> 		int left = n;
> 		int right = n;
> 		int result = 0;
> 
> 		if(NRabinMiller(n,8))
> 			cout << 0 << endl;
> 		else
> 		{
> 			while(--left)
> 			{
> 				if(NRabinMiller(left,8))
> 					break;
> 			}
> 			while(++right)
> 			{
> 				if(NRabinMiller(right,8))
> 					break;
> 			}
> 			cout << right-left << endl;
> 		}
> 	}
> 	return 0;
> }

• Re:请教int和__int64的区别 (74) skogt 2010-10-21 21:00:34