最大公约数&最小公倍数
Euclid's Algorithm：若(b
eq0)，那么(gcd(a,b)=gcd(b,a\%b))。
若(a<b)，定理会先交换a和b。
注意：0和任意正整数a的gcd是a。
int gcd(int a, int b) {
return !b ? a : gcd(b, a % b);
}
时间复杂度(O(lgb))，因为每次递归问题规模都会缩减一半以上。
最小公倍数(lcm=frac{a*b}{gcd})。
- 扩展欧几里得算法
可以计算出满足下式的三元组((d,x,y))：
[d = GCD(a, b) = ax + by
]
int Euclid_extend(int a, int b, int* x, int* y) {
if(0 == b) {
*x = 1;
*y = 0;
return a;
}
else {
int r = Euclid_extend(b,a%b,x,y);
int temp = *x;
*x = *y;
*y = temp - (*y)*(a/b);
return r;
}
}
简单证明：
(b=0)是递归基，易得一组解(x=1,y=0);
(b
eq0)时：
首先递归求解：
[d'=gcd(b,a\%b)=bx'+(a\%b)y' (1)
]
我们知道：
[d=gcd(a,b)=d'=gcd(b,a\%b) (2)
]
[a\%b=a-b*iggllfloor a/b iggr
floor (3)
]
将(2)(3)式带入(1)：
[d=bx'+(a-biggllfloor a/b iggr
floor)y'=ay'+b(x'-iggllfloor a/b iggr
floor y')
]
所以，令(x=y')、(y=x'-iggllfloor a/b iggr floor y')，就可以满足(d=ax+by)。
分数
PAT甲1088是比较经典的分数处理问题，求2个分数的和、差、积、商，输出最简形式。
表示、化简、运算、输出，代码阐释得很清楚。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
return !b ? a : gcd(b,a % b);
}
struct Fraction{
ll nume,deno;
};
Fraction reduction(Fraction a)
{
if(a.deno < 0)
{
a.deno = -a.deno;
a.nume = -a.nume;
}
if(a.nume == 0)
{
a.deno = 1;
}
else
{
int d = gcd(abs(a.nume),abs(a.deno));
a.nume /= d;
a.deno /= d;
}
return a;
}
Fraction add(Fraction a,Fraction b)
{
Fraction res;
res.deno = a.deno * b.deno;
res.nume = a.deno * b.nume + a.nume * b.deno;
return reduction(res);
}
Fraction sub(Fraction a,Fraction b)
{
Fraction res;
res.deno = a.deno * b.deno;
res.nume = a.nume * b.deno - a.deno * b.nume;
return reduction(res);
}
Fraction times(Fraction a,Fraction b)
{
Fraction res;
res.deno = a.deno * b.deno;
res.nume = a.nume * b.nume;
return reduction(res);
}
Fraction divide(Fraction a,Fraction b)
{
Fraction res;
res.deno = a.deno * b.nume;
res.nume = a.nume * b.deno;
return reduction(res);
}
void showFrac(Fraction a)
{
a = reduction(a);
if(a.nume < 0)
{
printf("(");
}
if(a.deno == 1)
{
printf("%lld",a.nume);
}
else if(abs(a.nume) > abs(a.deno))
{
printf("%lld %lld/%lld",a.nume / a.deno,abs(a.nume) % a.deno,a.deno);
}
else
{
printf("%lld/%lld",a.nume,a.deno);
}
if(a.nume < 0)
{
printf(")");
}
}
int main()
{
Fraction a,b;
scanf("%lld/%lld%lld/%lld",&a.nume,&a.deno,&b.nume,&b.deno);
showFrac(a);
printf(" + ");
showFrac(b);
printf(" = ");
showFrac(add(a,b));
printf("
");
showFrac(a);
printf(" - ");
showFrac(b);
printf(" = ");
showFrac(sub(a,b));
printf("
");
showFrac(a);
printf(" * ");
showFrac(b);
printf(" = ");
showFrac(times(a,b));
printf("
");
showFrac(a);
printf(" / ");
showFrac(b);
printf(" = ");
if(b.nume == 0)
{
printf("Inf
");
}
else
{
showFrac(divide(a,b));
printf("
");
}
return 0;
}
素数
1、判断素数
bool isPrime(int a)
{
if(a <= 1) //1不是素数，也不是合数
return false;
int tmp = (int)sqrt(1.0 * a);
for(int i = 2;i <= tmp;i++)
{
if(a % i == 0)
return false;
}
return true;
}
2、打素数表
第一种方法是枚举判断。
const int maxn = 10010;
int prime[maxn],num = 0;
void Prime_table()
{
for(int i = 2;i < maxn;i++)
{
if(isPrime(i))
{
prime[num++] = i;
}
}
}
第二种是Eratosthenes筛法，复杂度比枚举更优，代码更短。
/* sieve[k] is false iff k is a prime */
public static boolean[] primes (int n) {
boolean[] sieve = new boolean[n + 1];
sieve[0] = sieve[1] = true;
for (int k = 2; k * k <= n; ++k) {
if (!sieve[k]) {
for (int j = k * k; j <= n; j += k) {
sieve[j] = true;
}
}
}
return sieve;
}
3、分解质因子
注意：1要特判。
//存储
struct factor{
int x,cnt; //x为质因子,cnt为该质因子个数
}fac[20];
int num = 0; //记录不同因子个数
//枚举小于等于sqrt(n)内的所有质因子,判断哪个是n的因子
for(int i = 0;prime[i] <= sqrt(n);i++)
{
if(n % prime[i] == 0)
{
fac[num].x = prime[i];
fac[num].cnt = 0;
while(n % prime[i] == 0)
{
fac[num].cnt++;
n /= primep[i];
}
num++;
}
}
//如果n仍然大于1,说明n有一个大于sqrt(n)的质因子
if(n != 1)
{
fac[num].x = n;
fac[num++].cnt = 1;
}