推论1：方程ax=b(mod n)对于未知量x有解，当且仅当gcd(a,n) | b。
推论2：方程ax=b(mod n)或者对模n有d个不同的解，其中d=gcd(a,n)，或者无解。
定理1：设d=gcd(a,n)，假定对整数x和y满足d=ax+by(比如用扩展Euclid算法求出的一组解)。如果d | b，则方程ax=b(mod n)有一个解x0满足x0=x*(b/d) mod n 。特别的设e=x0+n，方程ax=b(mod n)的最小整数解x1=e mod (n/d)，最大整数解x2=x1+(d-1)*(n/d)。
定理2：假设方程ax=b(mod n)有解，且x0是方程的任意一个解，则该方程对模n恰有d个不同的解(d=gcd(a,n))，分别为：xi=x0+i*(n/d) mod n 。
证明过程请详见 《算法导论》
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int EXTENDED_EUCLID(int a,int b,int &x,int &y)//扩展欧几里德算法
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=EXTENDED_EUCLID(b,a%b,x,y);
int temp=x;
x=y;
y=temp-a/b*y;
return r;
}
int MODULAR_LINEAR(int a,int b,int n)//求解模线性方程
{
int d,x,y;
int x0;
d=EXTENDED_EUCLID(a,n,x,y);
x0=(x*(b/d)+n)%n;
return x0;
}
//当时鱼头让我们研究的时候，没有考虑得太仔细，上面的方程只能求出一个可行解
//而下面的函数能够求出最小的整数解，甚至在模n内任意的解
long long MODULAR_LINEAR(long long a,long long b,long long n)//求解模线性方程
{
long long d,x,y;
long long x0;
d=EXTENDED_EUCLID(a,n,x,y);
if(b%d)
return -1;
x0=(x*(b/d))%n+n;//确保是正数
x0%=(n/d);//x0是第一个大于0的整数解
return x0;
}
int CHINESE_RESIDUE_THEOREM(int n[],int b[],int k)//求解模线性方程组，所有数据从1号下标开始存储
{
int result=0;
int i;
int N=1;
int *m=new int [k+1];
int *reversem=new int [k+1];
int sum=0;
for(i=1;i<=k;i++)
{
N*=n[i];
}
for(i=1;i<=k;i++)
{
m[i]=N/n[i];
reversem[i]=MODULAR_LINEAR(m[i],1,n[i]);
sum+=m[i]*reversem[i]*b[i];
}
result=sum%N;
return result;
}
int main ()
{
int num;
int i;
printf("参考格式:X mod n[i] = b[i]\n");
cout<<"请输入方程的个数：";
cin>>num;
int *n=new int [num+1];
int *b=new int [num+1];
for(i=1;i<=num;i++)
{
cout<<"请输入第"<<i<<"个方程的n和b:";
cin>>n[i]>>b[i];
}
int result=CHINESE_RESIDUE_THEOREM(n,b,num);
cout<<"解为:";
cout<<result<<endl;
cout<<"谢谢你的使用"<<endl;
system("pause");
return 0;
}
摘要: 这道题直接模拟就好了，不过我有一点不明白的是，确定棋子的位置时两次的搜索顺序为什么不同？如果说要考虑玩家的视角的话，为什么输出的格式还是一样的呢？呵呵。值得一提的是:为了模拟这道题，我把所有的步骤分布来写了。1.初步读入数据，略去棋盘框架(input)；2.精确读入棋盘点每个棋子的信息,过滤(filter)；3.搜索(read)4.输出(print)不过值得注意的是：这样写代码会很长，看来怎么缩短...
阅读全文
这道题的大意是：
有n个党派，每个党派有一位主席，现在选举国家领导人，m个人投票，看看获胜的是那个党或者是个人；
PS:题目里没说清楚，就是每个党派只有一个候选人，这个要注意下，其它的没什么好说的了，此题不难。
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
map<string,string>mymap_party;
map<int,string>mymap_name;
map<string,int>mymap_index;
int votenum[1000000];
int main()
{
int i;
int n,m;
memset(votenum,0,sizeof(votenum));
scanf("%d",&n);
cin.ignore();
for(i=1;i<=n;i++)
{
string temp1;
string temp2;
getline(cin,temp1);
getline(cin,temp2);
mymap_party[temp1]=temp2;
mymap_name[i]=temp1;
mymap_index[temp1]=i;
}
scanf("%d",&m);
cin.ignore();
for(i=1;i<=m;i++)
{
string temp;
getline(cin,temp);
votenum[mymap_index[temp]]++;
}
int max=0;
int maxmark=0;
int secmax=0;
for(i=1;i<=n;i++)
{
if(votenum[i]>max)
{
secmax=max;
max=votenum[i];
maxmark=i;
}
else if(votenum[i]>secmax)
{
secmax=votenum[i];
}
}
string test("independent");
if(max==secmax)
printf("tie\n");
else if(max!=secmax&&mymap_party[mymap_name[maxmark]]==test)
cout<<mymap_name[maxmark]<<endl;
else
cout<<mymap_party[mymap_name[maxmark]]<<endl;
system("pause");
return 0;
}
摘要: 刚上完数据结构课，想练习一下邻接表以及拓扑排序，于是找到了这道题，没想到这道题远远不止拓扑排序这么简单，汗~PS:这道题用拓扑排序要特别注意，当度为零的点>1时，要判断图中是否有环。我就是错在这里，结果调了一个下午。
#include<iostream>#include<algorithm>#include<cassert>#include<cma...
阅读全文
1. 模板的概念。
我们已经学过重载(Overloading)，对重载函数而言,C++的检查机制能通过函数参数的不同及所属类的不同。正确的调用重载函数。例如，为求两个数的最大值，我们定义MAX()函数需要对不同的数据类型分别定义不同重载(Overload)版本。
//函数1.
int max(int x,int y);
{return(x>y)?x:y ;}
//函数2.
float max( float x,float y){
return (x>y)? x:y ;}
//函数3.
double max(double x,double y)
{return (c>y)? x:y ;}
但如果在主函数中，我们分别定义了 char a,b; 那么在执行max(a,b);时 程序就会出错，因为我们没有定义char类型的重载版本。
现在，我们再重新审视上述的max()函数，它们都具有同样的功能，即求两个数的最大值，能否只写一套代码解决这个问题呢？这样就会避免因重载函数定义不 全面而带来的调用错误。为解决上述问题C++引入模板机制，模板定义：模板就是实现代码重用机制的一种工具，它可以实现类型参数化，即把类型定义为参数， 从而实现了真正的代码可重用性。模版可以分为两类，一个是函数模版，另外一个是类模版。
2. 函数模板的写法
函数模板的一般形式如下：
Template <class或者也可以用typename T>
返回类型 函数名（形参表）
{//函数定义体 }
说明： template是一个声明模板的关键字，表示声明一个模板关键字class不能省略，如果类型形参多余一个 ，每个形参前都要加class <类型 形参表>可以包含基本数据类型可以包含类类型.
请看以下程序:
//Test.cpp
#include <iostream>
using std::cout;
using std::endl;
//声明一个函数模版,用来比较输入的两个相同数据类型的参数的大小，class也可以被typename代替，
//T可以被任何字母或者数字代替。
template <class T>
T min(T x,T y)
{ return(x<y)?x:y;}
void main( )
{
int n1=2,n2=10;
double d1=1.5,d2=5.6;
cout<< "较小整数:"<<min(n1,n2)<<endl;
cout<< "较小实数:"<<min(d1,d2)<<endl;
system("PAUSE");
}
程序运行结果：
程序分析：main()函数中定义了两个整型变量n1 , n2 两个双精度类型变量d1 , d2然后调用min( n1, n2); 即实例化函数模板T min(T x, T y)其中Ｔ为int型，求出n1,n2中的最小值．同理调用min(d1,d2)时，求出d1,d2中的最小值．
3. 类模板的写法
定义一个类模板：
Template < class或者也可以用typename T >
class类名｛
／／类定义．．．．．．
｝；
说明：其中，template是声明各模板的关键字，表示声明一个模板，模板参数可以是一个，也可以是多个。
例如：定义一个类模板：
// ClassTemplate.h
#ifndef ClassTemplate_HH
#define ClassTemplate_HH
template<typename T1,typename T2>
class myClass{
private:
T1 I;
T2 J;
public:
myClass(T1 a, T2 b);//Constructor
void show();
};
//这是构造函数
//注意这些格式
template <typename T1,typename T2>
myClass<T1,T2>::myClass(T1 a,T2 b):I(a),J(b){}
//这是void show();
template <typename T1,typename T2>
void myClass<T1,T2>::show()
{
cout<<"I="<<I<<", J="<<J<<endl;
}
#endif
// Test.cpp
#include <iostream>
#include "ClassTemplate.h"
using std::cout;
using std::endl;
void main()
{
myClass<int,int> class1(3,5);
class1.show();
myClass<int,char> class2(3,'a');
class2.show();
myClass<double,int> class3(2.9,10);
class3.show();
system("PAUSE");
}
最后结果显示：
4.非类型模版参数
一般来说，非类型模板参数可以是常整数（包括枚举）或者指向外部链接对象的指针。
那么就是说，浮点数是不行的，指向内部链接对象的指针是不行的。
template<typename T, int MAXSIZE>
class Stack{
Private:
T elems[MAXSIZE];
…
};
Int main()
{
Stack<int, 20> int20Stack;
Stack<int, 40> int40Stack;
…
};