推論1：方程ax=b(mod n)對于未知量x有解，當且僅當gcd(a,n) | b。
推論2：方程ax=b(mod n)或者對模n有d個不同的解，其中d=gcd(a,n)，或者無解。
定理1：設(shè)d=gcd(a,n)，假定對整數(shù)x和y滿足d=ax+by(比如用擴展Euclid算法求出的一組解)。如果d | b，則方程ax=b(mod n)有一個解x0滿足x0=x*(b/d) mod n 。特別的設(shè)e=x0+n，方程ax=b(mod n)的最小整數(shù)解x1=e mod (n/d)，最大整數(shù)解x2=x1+(d-1)*(n/d)。
定理2：假設(shè)方程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;
}
//當時魚頭讓我們研究的時候，沒有考慮得太仔細，上面的方程只能求出一個可行解
//而下面的函數(shù)能夠求出最小的整數(shù)解，甚至在模n內(nèi)任意的解
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;//確保是正數(shù)
x0%=(n/d);//x0是第一個大于0的整數(shù)解
return x0;
}
int CHINESE_RESIDUE_THEOREM(int n[],int b[],int k)//求解模線性方程組，所有數(shù)據(jù)從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<<"請輸入方程的個數(shù)：";
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.初步讀入數(shù)據(jù)，略去棋盤框架(input)；2.精確讀入棋盤點每個棋子的信息,過濾(filter)；3.搜索(read)4.輸出(print)不過值得注意的是：這樣寫代碼會很長，看來怎么縮短...
閱讀全文
這道題的大意是：
有n個黨派，每個黨派有一位主席，現(xiàn)在選舉國家領(lǐng)導人，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;
}
摘要: 剛上完數(shù)據(jù)結(jié)構(gòu)課，想練習一下鄰接表以及拓撲排序，于是找到了這道題，沒想到這道題遠遠不止拓撲排序這么簡單，汗~PS:這道題用拓撲排序要特別注意，當度為零的點>1時，要判斷圖中是否有環(huán)。我就是錯在這里，結(jié)果調(diào)了一個下午。
#include<iostream>#include<algorithm>#include<cassert>#include<cma...
閱讀全文
1. 模板的概念。
我們已經(jīng)學過重載(Overloading)，對重載函數(shù)而言,C++的檢查機制能通過函數(shù)參數(shù)的不同及所屬類的不同。正確的調(diào)用重載函數(shù)。例如，為求兩個數(shù)的最大值，我們定義MAX()函數(shù)需要對不同的數(shù)據(jù)類型分別定義不同重載(Overload)版本。
//函數(shù)1.
int max(int x,int y);
{return(x>y)?x:y ;}
//函數(shù)2.
float max( float x,float y){
return (x>y)? x:y ;}
//函數(shù)3.
double max(double x,double y)
{return (c>y)? x:y ;}
但如果在主函數(shù)中，我們分別定義了 char a,b; 那么在執(zhí)行max(a,b);時 程序就會出錯，因為我們沒有定義char類型的重載版本。
現(xiàn)在，我們再重新審視上述的max()函數(shù)，它們都具有同樣的功能，即求兩個數(shù)的最大值，能否只寫一套代碼解決這個問題呢？這樣就會避免因重載函數(shù)定義不 全面而帶來的調(diào)用錯誤。為解決上述問題C++引入模板機制，模板定義：模板就是實現(xiàn)代碼重用機制的一種工具，它可以實現(xiàn)類型參數(shù)化，即把類型定義為參數(shù)， 從而實現(xiàn)了真正的代碼可重用性。模版可以分為兩類，一個是函數(shù)模版，另外一個是類模版。
2. 函數(shù)模板的寫法
函數(shù)模板的一般形式如下：
Template <class或者也可以用typename T>
返回類型 函數(shù)名（形參表）
{//函數(shù)定義體 }
說明： template是一個聲明模板的關(guān)鍵字，表示聲明一個模板關(guān)鍵字class不能省略，如果類型形參多余一個 ，每個形參前都要加class <類型 形參表>可以包含基本數(shù)據(jù)類型可以包含類類型.
請看以下程序:
//Test.cpp
#include <iostream>
using std::cout;
using std::endl;
//聲明一個函數(shù)模版,用來比較輸入的兩個相同數(shù)據(jù)類型的參數(shù)的大小，class也可以被typename代替，
//T可以被任何字母或者數(shù)字代替。
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<< "較小整數(shù):"<<min(n1,n2)<<endl;
cout<< "較小實數(shù):"<<min(d1,d2)<<endl;
system("PAUSE");
}
程序運行結(jié)果：
程序分析：main()函數(shù)中定義了兩個整型變量n1 , n2 兩個雙精度類型變量d1 , d2然后調(diào)用min( n1, n2); 即實例化函數(shù)模板T min(T x, T y)其中Ｔ為int型，求出n1,n2中的最小值．同理調(diào)用min(d1,d2)時，求出d1,d2中的最小值．
3. 類模板的寫法
定義一個類模板：
Template < class或者也可以用typename T >
class類名｛
／／類定義．．．．．．
｝；
說明：其中，template是聲明各模板的關(guān)鍵字，表示聲明一個模板，模板參數(shù)可以是一個，也可以是多個。
例如：定義一個類模板：
// 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();
};
//這是構(gòu)造函數(shù)
//注意這些格式
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");
}
最后結(jié)果顯示：
4.非類型模版參數(shù)
一般來說，非類型模板參數(shù)可以是常整數(shù)（包括枚舉）或者指向外部鏈接對象的指針。
那么就是說，浮點數(shù)是不行的，指向內(nèi)部鏈接對象的指針是不行的。
template<typename T, int MAXSIZE>
class Stack{
Private:
T elems[MAXSIZE];
…
};
Int main()
{
Stack<int, 20> int20Stack;
Stack<int, 40> int40Stack;
…
};