Uva 10413 Crazy Savages

Tags: c++

Sol:

根据题意可列方程:

(c[i] + x*p[i])%m = (c[j] + x*p[j])%m,即:c[i] + x*p[i] = c[j] + x*p[j] + y*m(x,y为未知数)

此问题就转换成一元二次方程求解了,扩展欧几里得(题目已经给了N , M的范围,所以只需枚举即可)。

#include 
#include 
#include 

using namespace std;

const int maxn = 20 + 10;

int n;

int extend_gcd(int a,int b,int &x,int &y)
{
	if(a==0&&b==0)  return -1;
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	long long d=extend_gcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}

int C[maxn],P[maxn],L[maxn];

bool solve(int m)
{
	for(int i=0;i

本文链接:http://www.4byte.cn/learning/58683.html