首页 > ACM题库 > HDU-杭电 > hdu 2185 Chess-数论-[解题报告]C++
2013
12-30

hdu 2185 Chess-数论-[解题报告]C++

Chess

问题描述 :

The Association of Chess Monsters (ACM) is planning their annual team match up against the rest of the world. The match will be on 30 boards, with 15 players playing white and 15 players playing black. ACM has many players to choose from, and they try to pick the best team they can. The ability of each player for playing white is measured on a scale from 1 to 100 and the same for playing black. During the match a player can play white or black but not both. The value of a team is the total of players’ abilities to play white for players designated to play white and players’ abilities to play black for players designated to play black. ACM wants to pick up a team with the highest total value.

输入:

Input consists of a sequence of lines giving players’ abilities. Each line gives the abilities of a single player by two integer numbers separated by a single space. The first number is the player’s ability to play white and the second is the player’s ability to play black. There will be no less than 30 and no more than 1000 lines on input.

输出:

Input consists of a sequence of lines giving players’ abilities. Each line gives the abilities of a single player by two integer numbers separated by a single space. The first number is the player’s ability to play white and the second is the player’s ability to play black. There will be no less than 30 and no more than 1000 lines on input.

样例输入:

87 84
66 78
86 94
93 87
72 100
78 63
60 91
77 64
77 91
87 73
69 62
80 68
81 83
74 63
86 68
53 80
59 73
68 70
57 94
93 62
74 80
70 72
88 85
75 99
71 66
77 64
81 92
74 57
71 63
82 97
76 56

样例输出:

2506

这道题目有个地方有些坑啊   P是要大于N的 否则就是 找不到D的值,输出题目要求的 字符串

给你一个树,每个树的节点有 K个儿子,树的深度为D,总节点数 对P取模的值为N,  求树的深度D

列出方程 K^D%P=N,所以又是一道 解高次同余方程组的应用

算法原理 看poj3243的报告, http://blog.csdn.net/u010682557/article/details/14214207,原理都是一样的 

算法流程:

s1:i从0到100循环验证,如果满足Ai≡B(mod C),那么i就为所求,否则继续s2;

s2:令d=0,D=1,执行以下循环:

  1. while((tmp=gcd(A,C))!=1)  
  2. {  
  3.     if(B%tmp)return -1;//无解  
  4.     ++d;  
  5.     C/=tmp;  
  6.     B/=tmp;  
  7.     D=D*A/tmp%C;  
  8. }  



s3:令m=ceil(sqrt(C));

s4:i从0到m循环执行将(i,AI%C)插入Hash表中;

s5:求的K=quick_mod(A,m,C),令i=0,如果i>m执行s6;否则求DX=B(mod C)在 [0,C-1]的解,并在Hash中查询,若查到(假设是x),则返回 i*m+x,否则D=DK%C,i=i+1,继续循环:

s6:返回-1;

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;


#define inf 0xfffffff

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::iterator p;
//
//vector<int>G[30012];

#define maxn 65535

struct hash
{
	int a,b,nex;
}Hash[maxn*2];

int flg[maxn+66];
int top,idx;

void ins(int a,int b)
{
	int k=b&maxn;
	if(flg[k]!=idx)
	{
		flg[k]=idx;
		Hash[k].nex=-1;
		Hash[k].a=a;
		Hash[k].b=b;
	}
	while(Hash[k].nex!=-1)
	{
		if(Hash[k].b==b)return;
		k=Hash[k].nex;
	}
	Hash[k].nex=++top;
	Hash[top].nex=-1;
	Hash[top].a=a;
	Hash[top].b=b;
}

int find(int b)
{
	int k=b&maxn;
	if(flg[k]!=idx)return -1;
	while(k!=-1)
	{
		if(Hash[k].b==b)
			return Hash[k].a;
		k=Hash[k].nex;
	}
	return -1;
}

int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}

int exgcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	int r=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-a/b*y;
	return r;
}

int inval(int a,int b,int n)
{
	int x,y,e;
	exgcd(a,n,x,y);
	e=(long long)x*b%n;
	return e<0?e+n:e;
}

int powmod(long long a,int b,int c)
{
	long long ret=1%c;
	a%=c;
	while(b)
	{
		if(b&1)
			ret=ret*a%c;
		a=a*a%c;
		b>>=1;
	}
	return ret;
}

int babystep(int A,int B,int C)
{
	top=maxn;
	++idx;
	long long buf=1%C,D=buf,K;
	int i,d=0,tmp;
	for(i=0;i<=100;buf=buf*A%C,++i)
		if(buf==B)
			return i;
	while((tmp=gcd(A,C))!=1)
	{
		if(B%tmp)return -1;
		++d;
		C/=tmp;
		B/=tmp;
		D=D*A/tmp%C;
	}
	int M=(int)ceil(sqrt((double)C));
	for(buf=1%C,i=0;i<=M;buf=buf*A%C,++i)
		ins(i,buf);
	for(i=0,K=powmod((long long)A,M,C);i<=M;D=D*K%C,++i)
	{
		tmp=inval((int)D,B,C);
		int w;
		if(tmp>=0 && (w=find(tmp))!=-1)
			return i*M+w+d;
	}
	return -1;
}

int main(void)
{
	int A,B,C;
	while(scanf("%d %d %d",&A,&C,&B)==3)
	{
		if(C<B)//就是这里要注意了
		{
			puts("Orz,I can’t find D!");
			continue;
		}
		int ans=babystep(A,B,C);
		if(ans<0)
			puts("Orz,I can’t find D!");
		else
			printf("%d\n",ans);
	}
}

解题转自:http://blog.csdn.net/yitiaodacaidog/article/details/14231407


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  3. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示