noip中的数论数值14页.pptVIP

noip中的数论/数值 有关数学的函数 C/C++中有关数学的函数在math.h中。 使用时需要注意精度问题。 math.h中有个叫y0的函数，会与全局变量名冲突。 log()是数学中的ln，log10()是数学中的lg，没有logab的函数，需要用换底公式。 三角函数、对数函数等很慢。 尽量避免除法。 double有误差，pow(10,100)-(pow(10,100)+1)=0！ 二项式定理与杨辉三角 最大公约数与最小公倍数 最大公约数gcd(a,b)，也记为(a,b) 最小公倍数lcm(a,b) gcd(a,b)=gcd(b,a%b) lcm(a,b)=ab/gcd(a,b) 最大公约数与最小公倍数 int gcd(int a,int b) { int r; while(b) { r = a % b; a = b; b = r; } return a; } 欧拉函数 小于n且与n互质的数的个数 称为欧拉函数。 若n为素数则 欧拉函数 int phi(int n) { int ret = n,i; for(i = 2;i = n;++i) if(n % i == 0) { ret = ret * (i - 1) / i; while(n % i == 0) n /= i; } if(n 1) ret = ret * (n - 1) / n; return ret; } 复杂度O(logn) 同余 (a+b)%n=(a%n+b%n)%n a*b%n=(a%n)*(b%n)%n 快速幂 int pow(int a,int n,int p) { if(!n) return 1; int t = pow(a,n 1,p); t = t * t % p; if(n 1) t = t * a % p; return t } 复杂度O(logn)，有非递归写法，适用于高精度 同余方程 同余方程 求关于 x 同余方程 ax ≡ 1 (mod b)的最小正整数解。 ax ≡ 1 (mod b) =ax-1 ≡ 0 (mod b) =b|(ax-1) =ax-1=kb =ax-kb=1 同余方程 由定理可知，ax+by=c有解当且仅当c|gcd(a,b) 对于不定方程，已知一组解，设为（x0,y0) 则通解为： x=x0+kb y=y0-ka 所以最终的最小整数解为 (x%b+b)%b 。 欧几里德扩展定理 对于不完全为0的非负整数a,b那么存在唯一的整数x,y使得gcd(a,b)=ax+by。 typedef long long ll; void exgcd(ll a,ll b,ll x,ll y) { if(!b) { x = 1; y = 0; } else { gcd(b,a % b,y,x); y -= x * (a / b); } } 剩余系 a(an)的1~n次幂模n的值称为a在模n下的剩余系，即 如果 则称A为完全剩余系，否则称A为不完全剩余系或者缩系。 对于n，能得到完全剩余系的a的个数为 * * *