Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

WA的不行了,跪求大牛指正,不胜感激TOT

Posted by kensin2 at 2010-06-10 20:34:54 on Problem 3641
#include <iostream>

using namespace std;

__int64 square_mod(__int64 a, __int64 b, __int64 n)
{
	__int64 x = a % n;
	__int64 s = 1;

	while (b)
	{
		if (b & 1)
		{
			s *= x;
			s %= n;
		}
		x = (x * x) % n;
		b >>= 1;
	}

	return (s % n);
}

int pseudo(int n, int b)
{
	if (square_mod(b, n, n) == (b % n))
		return 1;
	
	return 0;
}

int miller(int n, int b)
{
	/* n - 1 = 2^s * t */
	int t = n - 1;
	int s = 0;
	int j;
	int result;

	if (n < 4)
		return 1;

	if (!(n & 1))
		return 0;

	while (!(t & 1))
	{
		t >>= 1;
		s++;
	}

	for (j = 0; j < s; j++)
	{
		result = square_mod(b, t, n);
		if (result == n - 1 || result == 1)
			return 1;
		t <<= 1;
	}

	return 0;
}

int main()
{
	int b, n;
	while (cin >> n >> b && (n || b))
	{
		if (miller(n, 2) && miller(n, 3)
           && miller(n, 5) && miller(n, 7)
           && miller(n, 11))
			cout << "no" << endl;
		else
		{
			if (pseudo(n, b))
				cout << "yes" << endl;
			else
				cout << "no" << endl;
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator