legendre_symbol.cpp

数值计算的例子和参考书籍

#include <iostream>
#include <vector>
using namespace std;

vector<int> pr;
const int sq = 33333;
vector<bool> sieve(sq, true);

int leg(int a, int p)
{
	// 3
	if(a >= p) return leg(a % p, p);
	if(a < 0) return leg((a + (2000000000 / p * p)) % p, p);
	
	// 2
	if(a == 1) return 1;

	// 4
	if(a == 2) return (((p * p - 1) / 8) & 1) ? -1 : 1;
	if(a == p - 1) return (((p - 1) / 2) & 1) ? -1 : 1;

	// 1/5
	int b = -1;
	for(vector<int>::iterator i = pr.begin(); i != pr.end(); ++i)
	{
		if((a % *i) == 0 )
		{
			b = *i;
			break;
		}
	}
	
	// 5
	if(b == -1 || a == b)
	{
		return leg(p, a) * (((((p - 1) * (a - 1) / 4)) & 1) ? -1 : 1);
	}
	
	// 1
	return leg(b, p) * leg(a / b, p);
}

int main(void)
{
	for(int n = 2; n < sq; ++n)
	{
		if(!sieve[n]) continue;
		for(int m = n + n; m < sq; m += n) sieve[m] = false;
		pr.push_back(n);
	}

	int N;
	cin >> N;
	for(int n = 1; n <= N; ++n)
	{
		cout << "Scenario #" << n << ":" << endl;
		int a, p;
		cin >> a >> p;
		cout << leg(a, p) << endl << endl;
	}
	return 0;
}