最小公倍数和最大公约数
GCD求法：
int gcd(int a,int b)
{
int temp;
if(a<b)/*交换两个数，使大数放在a上*/
{
temp=a;a=b;b=temp;
}
while(b!=0)/*利用辗除法，直到b为0为止*/
{
temp=a%b;
a=b;
b=temp;
}
return a;
}
也可用递归：
int Gcd(int a, int b)
{
if(b == 0)
return a;
return Gcd(b, a % b);
}
GCD的一些性质;
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a^b) % p = ((a % p)^b) % p
求a^n%p
long exp_mod(long a,long n,long b)
{
long t;
if(n==0) return 1%b;
if(n==1) return a%b;
t=exp_mod(a,n/2,b);
t=t*t%b;
if(n%2==1) t=t*a%b;
return t;
}
筛选法求素数：
#define Max 1000000
bool prime[Max];
void IsPrime()
{
prime[0]=prime[1]=0;prime[2]=1;
for(int i=3;i<max;i++)
prime[i]=i%2==0?0:1;
int t=(int)sqrt(Max*1.0);
for(int i=3;i<=t;i++)
if(prime[i])
for(int j=i*2;j<Max;j+=i)
prime[j]=0;
}
比赛中题目：
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1181
GCD 与 LCM：
#include <iostream>
using namespace std;
int GCD(int a,int b)
{
int min, max;
max=a>b?a:b;
min=a<b?a:b;
if(max%min==0)
return min;
else
return GCD(min,max%min);
}
int LCM(int a,int b)
{
return (a*b)/GCD(a,b);
}
int main()
{
int a,b;
while(cin>>a>>b)
{
cout<<LCM(a,b)<<" "<<GCD(a,b)<<endl;
}
}
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1468
筛法求素数：
#include <iostream>
#include <cmath>
#define Max 1000001
using namespace std;
bool prime[Max];
void IsPrime()
{
prime[0]=prime[1]=0;
prime[2]=1;
for(int i=3; i<Max; i++)
prime[i]=i%2==0?0:1;
for(int i=3; i<=(int)sqrt(Max*1.0); i+=2)
{
if(prime[i])
{
for(int j=i*2; j<Max; j+=i)
{
prime[j]=0;
}
}
}
}
int main()
{
int n;
IsPrime();
while(cin>>n&&n!=0)
{
int count=0;
for(int i=2;i<=n-1;i++)
{
if(prime[i]) count++;
}
cout<<count<<endl;
}
}
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1469
素数和模运算结合：
#include <iostream>
#include <cmath>
using namespace std;
long exp_mod(long a,long n,long b)
{
long t;
if(n==0) return 1%b;
if(n==1) return a%b;
t=exp_mod(a,n/2,b);
t=t*t%b;
if(n%2==1) t=t*a%b;
return t;
}
int is_prime(int n)
{
if (n == 2)
return 1;
if (n % 2 == 0)
return 0;
for (int i = 3; i * i <= n; i++)
if (n % i == 0)
return 0;
return 1;
}
int main()
{
long a,p;
while(cin>>p>>a&&a!=0&&p!=0)
{
if(!is_prime(p)&&(exp_mod(a,p,p)==a)) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
}
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1470
鸽巢原理的应用：
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int a,b,c,d,e;
int men_max,men_min;
while(cin>>a>>b>>c>>d>>e&&(a||b||c||d||e))
{
men_max=a-b*c-1;
men_min=a-d+e;
if(c<0) men_max=a;
if(e<=0)men_min=0;
if(men_min<=men_max) cout<<men_min<<" "<<men_max<<endl;
else cout<<"-1"<<endl;
}
}
这个题是鸽巢原理（抽屉原理）的初步应用，应做如下理解：
1.在求最大和最小的过程中，男生人数最多的时候即女生人数最小的时候，男生人数最少的时候即女生人数最大的时候；
2.B、C两个数是一个抽屉，抽屉数是B，女生最少人数即为B*C+1；（此时男生最大，为A-B*C-1）
3.D、E两个数是另一个抽屉，抽屉数是D，男生最少的人数即为E，女生最多为D-E；（此时男生最小，为A-D+E）
4.当女生<0即没有女生的时候，男生最少=最多=总人数；
5.当男生<0即没有男生的时候，男生最少=最多=0；
6.当最少人数小于等于最多人数的时候输出正确的；
7.其余一切情况皆为逻辑错误。
心得体会是，可以取反面情况理解，即：什么情况是不成立的。切忌两方面同时考虑，一会儿就晕了。。