数学笔记

1整数的唯一分解定理(如果A本身就是素数的话，那么本身就是分解式)

任意正整数都有且只有一种方式写出其素因子的乘积表达式。

A = (p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn) 其中pi均为素数;

A^B = p1^(k1*B) * p2^(k2*B)*...* pn^(kn*B);

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

#define MAXN 1010

int n;
int p[MAXN] , k[MAXN];

void solve(){
   int pos = 0;
   /*分解整数*/
   for(int i = 2 ; i*i <= n ; i++){
      if(n%i == 0){
        p[pos] = i;
        k[pos] = 0;
        while(!(n%i)){
           k[pos]++;
           n /= i;
        }
        pos++;
      }
   }
   /*特殊判断，如果n本身是素数的话那么上面的for循环是不执行的*/
   if(n != 1){
     p[pos] = n;
     k[pos++] = 1;
   }
}

int main(){
  scanf("%d" , &n);
  solve();
  return 0;
}

2 约数和公式

对于已经分解的整数A = (p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)

则A的所有因子之和为

sum = (1+p1+p1^2+p1^3+...p1^k1) * (1+p2+p2^2+p2^3+….p2^k2) * (1+p3+ p3^3+…+ p3^k3) * .... * (1+pn+pn^2+pn^3+...pn^kn)

则A^B的所有的因子之和为

sum = (1+p1+p1^2+...+p1^(a1*B)) *(1+p2+p2^2+...+p2^(a2*B)) *...*(1+pn+pn^2+...+pn^(an*B))

3 同余模公式

(a+b)%m=(a%m+b%m)%m

(a-b)%m=(a%m-b%m)%m

(a*b)%m=(a%m*b%m)%m

4 求n!中末尾0的个数

我们只需要观察1*2*3...n的因子中，因子5的个数就可以了。因为末尾0的个数，实际上反映了结果中因子10的个数，而10=2*5；由于在1*2*3...n中，含有因子2的个数始终是大于含有因子5的个数，所以10的个数实际上是由因子5的个数决定的，所以需要计算出含有因子5的个数就好了。（只要把5改成2就变成求含有因子2的个数）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

int solve(int n){
   if(n == 0)
     return 0;
   return n/5+solve(n/5);
}

int main(){
   int n;
   scanf("%d" , &n);  
   cout<<solve(n)<<endl;
   return 0;
}

5 排列组合公式

6 直线上的点的问题
1 假设直线为ax+by+c = 0，问直线上是否存在一个点x[x1,x2],y[y1,y2]，如果不存在整数解输出-1。
2 扩展欧几里德算法求出一对整数(x , y)，满足ax+by = gcd(a , b)，这里的x和y是整数但是不一定是正数。
a和b是系数，d是gcd(a , b)，x和y是求出的整数对。

void gcd(int64 a , int64 b , int64 &d , int64 &x , int64 &y){
    if(!b){
      d = a;
      x = 1;
      y = 0;
    }
    else{
      gcd(b , a%b , d , y , x);
      y -= x*(a/b);
    }
}

3 那么求出了d 和 x y之和，我们需要判断是否有整数解。
有结论：设a，b，c是任意整数，d = gcd(a , b)，方程ax+by = g的一对整数解是(x, y)，那么当c是d的倍数的时候ax+by+c = 0才有整数解，并且一组解为(x*c/d , y*c/d)，假设x0 = x*c/d , y0 = y*c/d , 那么任意解为(x0+k*b' , y0-k*a') , a' = a/d , b' = b/d , k取任意整数; 如果c不是d的倍数那么方程是去整数解。

7 三角形问题

三角形的4心
重心：三角形三条边的中线的交点
垂心：三角形三条高的交点
外心：三角形外接圆的圆心，是三条垂线的交点
内心：三角形内接圆的圆心，是三条角平分线的交点

一 重心的性质
1、重心到顶点的距离与重心到对边中点的距离之比为2︰1。
2、重心和三角形3个顶点组成的3个三角形面积相等。即重心到三条边的距离与三条边的长成反比。
3、重心到三角形3个顶点距离的平方和最小。
4、在平面直角坐标系中，重心的坐标是顶点坐标的算术平均，即其重心坐标为（(X1+X2+X3)/3，（Y1+Y2+Y3)/3。

二 外心的性质：
1、三角形的三条边的垂直平分线交于一点，该点即为该三角形外心。
2、若O是△ABC的外心，则∠BOC=2∠A（∠A为锐角或直角）或∠BOC=360°-2∠A（∠A为钝角）。
3、当三角形为锐角三角形时，外心在三角形内部；当三角形为钝角三角形时，外心在三角形外部；当三角形为直角三角形时，外心在斜边上，与斜边的中点重合。
4、计算外心的坐标应先计算下列临时变量：d1，d2，d3分别是三角形三个顶点连向另外两个顶点向量的点乘。c1=d2d3，c2=d1d3，c3=d1d2；c=c1+c2+c3。重心坐标：( (c2+c3)/2c，(c1+c3)/2c，(c1+c2)/2c )。
5、外心到三顶点的距离相等

三 垂心的性质：
1、三角形三个顶点，三个垂足，垂心这7个点可以得到6个四点圆。
2、三角形外心O、重心G和垂心H三点共线，且OG︰GH=1︰2。（此直线称为三角形的欧拉线（Euler line））
3、垂心到三角形一顶点距离为此三角形外心到此顶点对边距离的2倍。

四 内心的性质：
1、三角形的三条内角平分线交于一点。该点即为三角形的内心。
2、直角三角形的内心到边的距离等于两直角边的和减去斜边的差的二分之一。
3、P为ΔABC所在平面上任意一点，点I是ΔABC内心的充要条件是：向量PI=(a×向量PA+b×向量PB+c×向量PC)/(a+b+c).
4、O为三角形的内心，A、B、C分别为三角形的三个顶点，延长AO交BC边于N，则有AO:ON=AB:BN=AC:CN=(AB+AC):BC

1 到三角形三定点值和最小的点----费马点
2 到三角形三顶点距离的平方和最小的点----重心
3 到三角形三边距离之积最大点----重心
4 到三角形三边距离平方和最小----重心的等角共轭点。

8 数根

1 如果把一个大数的各位数字相加得到一个和，再把这个和的各位数字相加又得一个和，再继续作数字和，直到最后的数字和是个位数为止，这最后的数称为最初那个数的“数字根”。比如d(2345) = d(14) = d(5)，那么2345的数根就是5。

2 一个数的数根就是它除以9的余数。d(x) = x%9 != 0 ? x%9 : 9；注意如果是x%9 = 0 , 那么数根为9.

9 [1,n]这个区间任意三个整数A ， B ， C，满足A*B = C的个数为(n/1+n/2+...+n/n)；
比如[1,4]，之间满足A*B = C的数
1*1 =1 , 1*2 = 2 , 1*3 = 3 , 1*4 = 5;
2*1 = 2 , 2*2 = 4;
3*1 = 3;
4*1 = 4;

总共8个 = 4/1+4/2+4/3+4/4