2017年ACM模板（常用）弱渣整理 五、数学相关

一、大数问题：

1.大数积

#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> using namespace std; char c[40]; typedef long long LL; void multiply(const char *a,const char *b)//大数相乘 { int i,j,ca,cb,*s; ca=strlen(a); cb=strlen(b); s=(int *)malloc(sizeof(int)*(ca+cb)); //分配存储空间 for (i=0;i<ca+cb;i++) s[i]=0; // 每个元素赋初值0 for (i=0;i<ca;i++) for (j=0;j<cb;j++) s[i+j+1]+=(a[i]-'0')*(b[j]-'0'); for (i=ca+cb-1;i>=0;i--) // 这里实现进位操作 if (s[i]>=10) { s[i-1]+=s[i]/10; s[i]%=10; } i=0; while(s[i]==0) i++; // 跳过头部0元素 for (j=0;i<ca+cb;i++,j++) c[j]=s[i]+'0'; c[j]='\0'; for (j=0;j<ca+cb;j++) cout<<c[j]; } int main() { int T; scanf("%d",&T); int kase = 0; while(T--) { char a[20], b[20]; LL t; scanf("%s%s",a, b); multiply(a,b); printf("\n"); } return 0; }

2.大数和

void BigInteger_Add(char *a, char *b) { //先进行每位的相加 for(int i=strlen(a)-1, j=strlen(b)-1; j>=0; j--, i--) { a[i] = a[i]+b[j]-'0'; } for(int i=strlen(a)-1; i>0; i--) { //每位进行判断是否大于9，如果大于则进位，自身减10 if(a[i] > '9') { a[i-1]++; a[i] = a[i]-10; } } //最后判断一下首位的数是否大于9 if(a[0]>'9') { a[0] -= 10; printf("1"); } printf("%s",a); return; }

3.大数求幂

LL mod(char *a, LL n) { LL ans = 0; int len = strlen(a); for(int i=0; i<len; i++) { ans = (((long long)ans*10 + a[i] - '0') % n); } return ans; }

---

二、最大公约数

定理：如果任意整数a和b不都为0，,则gcd(a,b)是a和b的线性组合集{ax+by: x,y∈Z }中的最小正元素。

性质： 1.gcd(a,b) = gcd(b,a) 2.gcd(a,b) = gcd(-a,b) 3.gcd(a,b) = gcd( |a| , |b| ) 4.gcd(a,0) = |a| 5.gcd(a,ka) = |a| 对任意k∈Z

推论1：对任意整数a与b，如果d|a且d|b，则d|gcd(a,b)。 推论2：对任意整数a与b以及任意非负整数n，有gcd(an,bn) = n gcd(a,b)。

求最大公约数（辗转相除）：

int gcd(int a,int b) { return b==0 ? a : gcd(b , a % b); }

---

三、互质数：

如果两个整数a和b的公约数只有1，即gcd(a,b)=1，则a与b称为互质数。

性质： 1.对于任意整数a、b和p，如果gcd(a,p)=1且gcd(b,p)=1，则gcd(ab,p)=1。 2.如果a与b互为质数，那么a+b 和 a*b 也互为质数。

---

四、素数：

素数的判断：

int is_prime(int p) { int k = sqrt(p+0.5); for(int i=2; i<=k; i++) { if(p%i) return 0; } return 1; }

素数筛法

#include<cstdio> #include<cstring> #include<cmath> using namespace std; const int maxn = 10000000; int vis[maxn]; typedef long long L; void Eratosthenes(L n) { memset(vis,0,sizeof(vis)); L m = sqrt(n + 0.5); for(L i=2; i<=m; i++) { if(!vis[i]) { for(L j=i*i; j<=n; j+=i) { vis[j] = 1; } } } return; } int main() { L n; scanf("%lld",&n); Eratosthenes(n); for(L i=2; i<=n; i++) { if(!vis[i]) { printf("%lld ",i); } } return 0; }

无平方因子的数：

#include<cstdio> #include<cstring> #include<cmath> using namespace std; typedef long long LL; const LL maxn = 1000000000000; int vis[maxn], ans[maxn]; LL n, m; int main() { int n,m; memset(vis,0,sizeof(vis)); int t=sqrt(maxn+0.5); for(int i=2;i<=t;i++) if(!vis[i]) for(int j=i*i; j<=maxn; j+=i) vis[j]=1; //先筛素数 while(scanf("%d%d",&n,&m) == 2 && n && m) { int k = floor(sqrt(m+0.5)); memset(ans, 0, sizeof(ans)); for(int i=2; i<=k; i++) if(!vis[i]) { int last = m / (i*i); for(int crt=n/(i*i); crt<=last; crt++) ans[(i*i)*crt]=1; }//筛无平方因子数 int count=0; for(int i=n; i<=m; i++) { if(!ans[i]) { printf("%d ",i); count++; } } printf("\n"); printf("%d\n",count); } return 0; }

---

五、扩展欧几里得算法：

问题：直线上的点：求直线ax+by+c=0上有多少个整点(x,y)满足x∈[x1,x2]，y∈[y1,y2]。

扩展欧几里得算法：找出一对整数(x,y)，使得ax+by=gcd(a,b)。这里的x和y不一定是整数，也可能是0或负数。 ax+by = gcd(a,b)这个式子总是有解。

原问题是求ax+by+c=0的解。移项得ax+by = -c。那么如果c是gcd(a,b)的倍数，那么就一定有解。 设a,b,c为任意整数，g = gcd(a,b)，方程ax+by=g的一组解是(x0,y0)，则当c是g的倍数时，ax+by=c的一组解是(x0c/g , y0c/g)；当c不是g的倍数时无整数解。

#include<cstdio> using namespace std; const int INF = 1000; void gcd(int a, int b, int &d, int &x, int &y) { if(!b) { d = a; x = 1; y = 0; }else{ gcd(b, a%b, d, y, x); y -= x*(a/b); } } int main() { int a,b,c,d; scanf("%d%d%d",&a,&b,&c); int x1,x2,y1,y2; scanf("%d%d%d%d",&x1,&x2,&y1,&y2);//整点的范围 int x0,y0; //ax+by=gcd(a,b)的一个解 gcd(a,b,d,x0,y0); int a2 = a/d, b2 = b/d; //其他解 int count = 0; if(c%d==0) { for(int k=0; k<INF; k++) { x0 = x0+k*b2; y0 = y0-k*a2; if(x0<x1||x0>x2||y0<y1||y0>y2) continue; count++; } } printf("%d\n",count); return 0; }

---

六、同余与模运算

几个公式：

1. (a+b) mod n = ((a mod n) + (b mod n)) mod n 2. (a-b) mod n = ((a mod n) - (b mod n) + n) mod n 3. ab mod n = (a mod n)(b mod n) mod n

大数取模上面有

幂取模：

int pow_mod(int a, int b, int n) { if(b == 0) return 1; int x = pow_mod(a, b/2, n); long long ans = (long long)x * x % n; if(b%2 == 1) ans = ans * a % n; return (int) ans; }

七、 线段性质

叉积公式：p1=(x1, y1)，p2=(x2,y2)。那么p1×p2 = x1y2 - x2y1。 问题： 1. 对于给定的两个有向线段p0p1和p0p2，相对于它们的公共端点p0来说，p0p1是否在p0p2的顺时针方向？

对于给定的两个线段p0p1和p1p2，如果先沿着p0p1再沿着p1p2前进，那么在点p1处是向左转还是向右转怎么判断。

线段p1p2和p3p4是否相交？

问题一：

根据上面的叉积公式我们可以通过求(p1 - p0) × (p2 - p1) 判断值的正负性从而判断出p0p1是在p0p2的顺时针还是逆时针。

问题二：

只需判断一下有向线段p0p2是位于p0p1的顺时针方向还是逆时针方向就可以了。所以计算一下(p2 - p0) × (p1 - p0)，判断值的正负性即可，如果为负，则p0p2位于p0p1的逆时针方向，在p1处左转，同理为正，则顺时针，右转。

问题三：

判断两线段是否相交，需要检查每条线段是否跨越了包含另一条线段的直线。如果点p1位于某条直线的一边，而点p2位于该直线的另一边，则称p1p2跨越了这条边。

#include<cstdio> #include<algorithm> using namespace std; struct Node{ int x, y; }; int Direction(Node a, Node b, Node c) { return (c.x-a.x) * (b.y-a.y) - (b.x-a.x) * (c.y - a.y); } bool OnSegment(Node a, Node b, Node c) { if(min(a.x,b.x) <= c.x && c.x <= max(a.x,b.x) && min(a.y, b.y) <= c.y && c.y <= (a.y, b.y)) { return true; } else return false; } bool SegmentIntersect(Node p1, Node p2, Node p3, Node p4) { int d1 = Direction(p3, p4, p1); int d2 = Direction(p3, p4, p2); int d3 = Direction(p1, p2, p3); int d4 = Direction(p1, p2, p4); if((d1<0&&d2>0) || (d1>0&&d2<0) || (d3<0&&d4>0) || (d3>0&&d4<0)) { return true; } else if(d1==0 && OnSegment(p3, p4, p1)) { return true; } else if(d2==0 && OnSegment(p3, p4, p2)) { return true; } else if(d3==0 && OnSegment(p1, p2, p3)) { return true; } else if(d4==0 && OnSegment(p1, p2, p4)) { return true; } else return false; } int main() { Node a, b, c, d; printf("输入两条直线："); printf("直线ab:\n"); printf("点a:"); scanf("%d%d",&a.x,&a.y); printf("点b:"); scanf("%d%d",&b.x,&b.y); printf("直线cd:\n"); printf("点c:"); scanf("%d%d",&c.x,&c.y); printf("点d:"); scanf("%d%d",&d.x,&d.y); if(SegmentIntersect(a,b,c,d)) { printf("ab与cd相交\n"); }else{ printf("ab与cd不相交\n"); } return 0; }

---

八、 极角排序

int cmp2(const Node &a, const Node &b) { return atan2(1.0*(a.y-u.y), 1.0*(a.x-u.x)) < atan2(1.0*(b.y-u.y), 1.0*(b.x-u.x)); }

---

九、 求凸包

#include<cstdio> #include<stack> #include<algorithm> #include<cmath> using namespace std; const int maxn = 1000; struct Node{ int x,y; }u,node[maxn]; int N; /*先按y排序*/ int cmp1(const Node &a, const Node &b) { return a.y < b.y; } /*极角排序*/ int cmp2(const Node &a, const Node &b) { return atan2(1.0*(a.y-u.y), 1.0*(a.x-u.x)) < atan2(1.0*(b.y-u.y), 1.0*(b.x-u.x)); } int Direction(Node a, Node b, Node c) { return (c.x-a.x) * (b.y-a.y) - (b.x-a.x) * (c.y - a.y); } bool right(Node a, Node b, Node c) { if(Direction(a, b, c) < 0) { return true; } else return false; } int main() { scanf("%d",&N); for(int i=0; i<N; i++) { scanf("%d%d",&node[i].x, &node[i].y); } sort(node, node+N, cmp1); stack<Node> s; s.push(node[0]);//先取y最小的点放入栈中 u = node[0]; sort(node+1, node+N, cmp2);//极角排序一下 s.push(node[1]); s.push(node[2]); for(int i=3; i<N; i++) { Node top = s.top(); s.pop(); Node n_top = s.top(); if(right(node[i], top, n_top)) { s.push(node[i]); } else{ s.push(top); s.push(node[i]); } } while(!s.empty()) { printf("%d %d\n",s.top().x, s.top().y); s.pop(); } return 0; }

若求一个点集中两点间最远距离——一定是凸包上的点