查找数字规律公式的网站:  http://oeis.org/A005773

 

C++头文件:    #include <bits/stdc++>

链接:  http://blog.kuoe0.tw/posts/2014/01/31/install-gnu-gcc-on-os-x-and-use-the-header-bits-stdcplusplus-h-and-policy-based-data-structure/

 

一个数论讲的很好的博客:  http://www.cnblogs.com/linyujun/category/784324.html

 

辗转相除法:

1.最大公约数

1 int gcd(int a,int b){2     if(b==0)3         return a;4     return gcd(b,a%b);5 }

1 LL gcd(LL a, LL b) 2 { 3     return b == 0? a : gcd(b, a % b); 4 } 5  6 void ex_gcd(LL a, LL b, LL& d, LL& x, LL& y) 7 { 8     if(!b) 9     {10         d = a;11         x = 1; 12         y = 0;13     }14     else 15     {16         ex_gcd(b, a % b, d, y, x);17         y -= x * (a/b);18     }19 }

 

 

2.扩展欧几里德算法

ax+by=gcd(a,b)

1 int extgcd(int a,int b,int &x,int &y){ 2     int d=a; 3     if(b!=0){ 4         d=extgcd(b,a%b,y,x); 5         y-=(a/b)*x; 6     } 7     else{ 8         x=1; 9         y=0;10     }11     return d;12 }

 

 

有关素数的基础算法:

1.素数判定

1 //素性测试 2 bool prime(int n){ 3     for(int i=2; i*i<=n; i++){ 4         if(n%i==0) 5             return false; 6     } 7     return n!=1;  //1是例外 8 } 9 10 //约数枚举11 vector
     
       dis(int n){12     vector
      
        res;13     for(int i=1; i*i<=n; i++){14         if(n%i==0){15             res.push_back(i);16             if(i!=n/i)17                 res.push_back(n/i);18         }19     }20     return res;21 }22 23 //整数分解24 map
       
         prime(int n){25     for(int i=2; i*i<=n; i++){26         while(n%i==0){27             ++res[i];28             n/=i;29         }30     }31     if(n!=1)32         res[n]=1;33     return res;34 }
       
      
     

 

 

2.埃氏筛法

1 int prime[MAX_N]; //第i个素数 2 bool is_prime[MAX_N+1]   //is_prime[i]为true表示i是素数 3  4 //返回n以内素数的个数 5 int solve(int n){ 6     int p=0; 7     for(int i=0; i<=n; i++) 8         is_prime[i]=true; 9     is_prime[0]=is_prime[1]=false;10     for(int i=2; i<=n; i++){11         if(is_prime[i]){12             prime[p++]=i;13             for(int j=2*i; j<=n; j+=i)14                 is_prime[i]=false;15         }16     }17     return p;18 }

 

3. 区间筛法

1 typedef long long ll; 2  3 bool is_prime[MAX_L]; 4 bool is_prime_small[MAX_B]; 5  6 //对区间[a,b)内的整数执行筛法.is_prime[i-a] = true  --  i是素数 7 void segment_sieve(ll a,ll b){ 8     for(int i=0; (ll)i*i

 

 

模运算

1 LL qpow(LL x, LL k) 2 { 3     LL res = 1; 4     while(k) 5     { 6         if(k & 1) res = res * x % MOD; 7         x = x * x % MOD; 8         k >>= 1; 9     }10     return res;11 }12 13 LL inv(LL a, LL x)14 {15     return qpow(a, x - 2);16 }

 

 

凸包:

 

1 struct point  2 {  3     double x;  4     double y;  5     point (double x = 0, double y = 0):x(x), y(y)  6     {}  7 };  8 typedef point Vector;//向量  9 Vector operator + (Vector A, Vector B)//向量加法 10 { 11     return Vector(A.x + B.x, A.y + B.y); 12 } 13  14 Vector operator - (Vector A, Vector B)//向量减法 15 { 16     return Vector(A.x - B.x, A.y - B.y); 17 } 18  19 Vector operator * (Vector A, double p)//向量乘法 20 { 21     return Vector(A.x * p, A.y * p); 22 } 23  24 Vector operator / (Vector A, double p)//向量除法 25 { 26     return Vector(A.x / p, A.y / p); 27 } 28  29 int dcmp(double x)//精度控制 30 { 31     if(fabs(x) < eps) return 0; 32     else  33         return x < 0? -1 : 1; 34 } 35  36 bool operator == (const point& a, const point& b)//判断点相等 37 { 38     return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; 39 } 40  41 double Dot(Vector A, Vector B)//向量点积，A*B，垂直为0 42 { 43     return A.x * B.x + A.y * B.y; 44 } 45  46 double Length(Vector A)//向量长度 47 { 48     return sqrt(Dot(A, A)); 49 } 50  51 double Angle(Vector A, Vector B)//向量极角 52 { 53     return acos(Dot(A, B) / Length(A) / Length(B)); 54 } 55  56 double Cross(Vector A, Vector B)//向量叉乘，AXB， 有向面积的两倍 57 { 58     return A.x * B.y - A.y * B.x; 59 } 60  61 double Area2(point A, point B, point C)//两向量组成的四边形的有向面积 62 { 63     return Cross(B - A, C - A); 64 } 65 Vector Rotate(Vector A, double rad)//向量A，逆时针旋转rad°， 极角形式 66 { 67     return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad)); 68 } 69  70 Vector Normal(Vector A)//A will not 0 Vector!， 求单位向量 71 { 72     double L = Length(A); 73     return Vector(A.x / L, A.y / L); 74 } 75  76 Vector GetLineIntersection(point P, Vector v, point Q, Vector w)//求两向量的交点（不求具体坐标） 77 { 78     Vector u = P - Q; 79     double t = Cross(w, u) / Cross(v, w); 80     return P + v * t; 81 } 82  83 double DistanceToLine(point P, point A, point B)// 点到直线的距离 84 { 85     Vector v1 = B - A, v2 = P - A; 86     return fabs(Cross(v1, v2)) / Length(v1); 87 } 88  89 double DistanceToSegment(point P, point A, point B)//点到线段的距离 90 { 91     if(A == B) return Length(P - A); 92     Vector v2 = P - A, v3 = P - B, v1 = B - A; 93     if(dcmp(Dot(v1, v2) < 0)) return Length(v2); 94     else if(dcmp(Dot(v1, v3)) > 0) return Length(v3); 95     else  96         return fabs(Cross(v1, v2)) / Length(v1); 97 } 98  99 point GetLineProjection(point P, point A, point B)//求点在直线上的投影100 {101     Vector v = B - A;102     return A + v * (Dot(v, P - A) / Dot(v, v));103 }104 105 bool SegmentProperIntersection(point a1, point a2, point b1, point b2)//两线段是否相交106 {107     double c1 = Cross(a2 - a1, b1 - a1);108     double c2 = Cross(a2 - a2, b2 - a1);109     double c3 = Cross(b2 - b1, a1 - b1);110     double c4 = Cross(b2 - b1, a2 - b1);111     return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;112 }113 114 bool OnSegment(point P, point a1, point a2)// 点是否在线段上115 {116     return dcmp(Cross(a1 - P, a2 - P)) == 0 && dcmp(Dot(a1 - P, a2 - P)) < 0;117 } 118 119 double PolygonArea(point *p, int n)// 凸多边形（多边形）的有向面积120 {121     double area = 0;122     for(int i = 1; i < n - 1;  i ++)123     area += Cross(p[i] - p[0], p[i + 1] - p[0]);124     return area / 2.0;125 }

 

 

正多边形内接圆半径:

1 double getlen(double n,double r/){  //n正多边形边数,r正多边形边长2      return 2.0*r*tan(pi/n);   //const int PI = acos (-1.0);3 }

 

 

 中国剩余定理模板:  http://blog.csdn.net/qq_32734731/article/details/51182391 

 

 

 

 数论可学习的链接:    http://www.cnblogs.com/linyujun/category/784324.html

 

 

 

 

 模板来自 : -> 萌哒哒~毅哥

<<挑战程序设计竞赛>>读后感......