过硬的基础就好比在武侠小说中拥有非凡的内功一样,只有将内力提升了,才能在使出华丽的招式的同时带来巨大的杀伤力。这对于ACM来说也是一样的道理,平时做好了基础知识的积累,还有对一些常用的函数和算法进行建库,在后来的使用中就能如鱼得水,达到事半功倍的效果。所以我会为每部分相关内容建立一些基础类及函数,并且在不断的学习中逐渐完善这些内容。
//┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
//┃ 文件名:Number Therory.h ┃
//┃ 实现功能:定义基础数论的一些类和函数 ┃
//┃ 导航: ┃
//┃ int gcd ( int, int ); 求两数的最大公约数( Greatest Common Divisor ) ┃
//┃ int lcm ( int, int ); 求两数的最小公倍数( Least Common Multiple ) ┃
//┃ int modExp( int, int, int ); 求a的b次方模n的结果 ( a^b %n ) ┃
//┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
#ifndef NUMBER_THEORY
#define NUMBER_THEORY
#pragma once
namespace ACM
{
// 获得两个整数的最大公约数,使用跌代版实现
int gcd( int a, int b );
// 获得两个整数的最小公倍数
int lcm( int a, int b );
// 计算 a的b次方模n的结果( a^b %n )
int modExp( int a, int b, int r )
}
#endif // NUMBER_THEORY
//┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
//┃ 文件名:Number Theory.cpp ┃
//┃ 实现功能:实现基础数论的一些算法 ┃
//┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
#include "Number Theory.h"
namespace ACM
{
// 使用迭代法实现
int gcd( int a, int b)
{
// 这里必须引入一个临时变量,否则 a=b, b=a%b 的话,由于a=b在前,那么进行b=a%b运
// 算时,由于a==b,所以结果必然为0
for ( int Temp=b; b!=0; Temp=a,a=b, b=Temp%b );
return a;
}
int lcm( int a, int b )
{
if ( a*b==0 ) // 如果其中一个数是0,那么最小公倍数是0
return 0;
return a*b / gcd(a,b); // 这里利用了最小公倍数和最大公约数的性质来求取最小公倍数
}
// 求a的b次方模n的结果 ( a^b %n )
// 主要考虑到a的b次方可能是一个很大的数字,直接求起结果很可能会导致溢出,所以需要
// 使用特殊的算法求解结果
int modExp( int a, int b, int r )
{
int Result=1;
while( b!=0 )
{
if ( b%2==1 )
Result = Result*a %r;
a = a * a % r;
b = b / 2;
}
return Result;
}
完善中.....
}