数学问题的解题方法(模板)

查找数字规律公式的网站: 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<int> dis(int n){
12     vector<int> 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<int,int> 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<b; i++)
 9         is_prime_small[i]=true;
10     for(int i=0; i<b-a; i++)
11         is_prime[i]=true;
12     for(int i=2; (ll)i*i<b; i++){
13         if(is_prime_small[i]){
14             for(int j=2*i; (ll)j*j<b; j+=i)
15                 is_prime_small[j]=false;  //筛[2,根号b)
16             for(ll j=max(2LL,(a+i-1)/i)*i; j<b; j+=i)
17                 is_prime[j-a]=false; //筛[a,b)
18         }
19     }
20 }

模运算

 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

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

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