13级个人结业赛-数学场

数学场题解。(现学现卖，有缺漏之处，还望包涵。)

从题目的分布上来看，A,B,C为数论内容,DFI为计算几何,E为矩阵,G题概率。希望你们在本次比赛中有所收获。

数学A

对于传统的ax+by=gcd(a,b)使用扩展欧几里得解即可,但是这边题面是ax+by+c=0

必然存在着差异。当我们求出ax+by=gcd(x,y)题解(x0,y0)的时候,ax+by+c=0的解就是

( x0*(-c/gcd(a,b)), y0*(-c/gcd(a,b))); 假如c%gcd(a,b)!=0那么算出来的解就不是整数解了，也就是无解的情况。

这边给出一个博客供大家学习:http://blog.csdn.net/daniel_ustc/article/details/8273201

 1 #include <iostream>  
 2 #include <stdio.h>  
 3 #include <stdlib.h>  
 4 #include <math.h>  
 5 #include <string.h>  
 6 #include <algorithm>  
 7 using namespace std;  
 8 typedef long long ll;  
 9 const ll maxn=5000000000000000000;  
10 int is(ll a,ll b)  
11 {  
12     if(fabs(a)<=maxn&&fabs(b)<=maxn) return 1;  
13     return 0;  
14 }  
15 ll gcd_ex(ll a,ll b,ll *x,ll *y)  
16 {  
17     if(b==0)  
18     {  
19         *y=0;  
20         *x=1;  
21         return a;  
22     }  
23     ll r=gcd_ex(b,a%b,x,y);  
24     ll t=*x;  
25     *x=*y;  
26     *y=t-a/b*(*y);  
27     return r;  
28 }  
29     
30 int main()  
31 {  
32     ll a,b,c,x,y,gcdans;  
33     while(scanf("%lld%lld%lld",&a,&b,&c)!=EOF)  
34     {  
35         gcdans=gcd_ex(a,b,&x,&y);  
36         if(c%gcdans==0)  
37         {  
38             x*=(-c)/gcdans;  
39             y*=(-c)/gcdans;  
40         }  
41         else
42         {  
43             printf("%lld %lld
",maxn+1,maxn+1);  
44             continue;  
45         }  
46         printf("%lld %lld
",x,y);  
47     }  
48     return 0;  
49 }

拙计的代码

　　　　　　　　　　　　　　　　　　　　　　　　　　数学B

求n=a*b*c因子个数。首先对n进行质因数分解。比如n=p1^x1*p2^x2….pk^xk ,p1,p2,p3…pk为质数。

那么他的因子就会有(x1+1)*(x2+1)*…*(xk+1)种组合；记得记忆化。不然会超时。

 1 #include <iostream> 
 2 #include <stdio.h> 
 3 #include <stdlib.h> 
 4 #include <math.h> 
 5 #include <string.h> 
 6 #include <algorithm> 
 7 using namespace std; 
 8 typedef long long ll; 
 9 const int maxn=1000005; 
10 ll a,b,c,num[maxn]= {0},prime[maxn]= {0},status[maxn]= {0}; 
11 const ll mod=1073741824; 
12 int workprime() 
13 { 
14     int ans=0; 
15     for(int i=2; i<=maxn; i++) 
16     { 
17         if(!status[i]) 
18         { 
19             prime[ans++]=i; 
20             status[i]=1; 
21             for(int j=i; j<=maxn; j+=i) 
22                 status[j]=1; 
23         } 
24     } 
25     return ans; 
26 } 
27 void count(ll r) 
28 { 
29     int ans=r; 
30     if(!num[r]) 
31     { 
32         int b=0; 
33         num[ans]=1; 
34         while(r>=prime[b]) 
35         { 
36             int cou=0; 
37             while(r%prime[b]==0) 
38             { 
39                 cou+=1; 
40                 r/=prime[b]; 
41             } 
42             b++; 
43             num[ans]=num[ans]*(cou+1); 
44             if(r==1) break; 
45         } 
46     } 
47 } 
48 int main() 
49 { 
50     ll sum=0,len; 
51   
52     memset(prime,0,sizeof(prime)); 
53     len=workprime(); 
54     memset(num,0,sizeof(num)); 
55     while(scanf("%lld%lld%lld",&a,&b,&c)!=EOF) 
56     { 
57         sum=0; 
58         for(ll i=1; i<=a; i++) 
59         { 
60             for(ll j=1; j<=b; j++) 
61             { 
62                 for(ll k=1; k<=c; k++) 
63                 { 
64                     count(i*j*k); 
65                     sum=(sum%mod+num[i*j*k])%mod; 
66                 } 
67             } 
68         } 
69         printf("%lld
",sum); 
70     } 
71     return 0; 
72 }

View Code

数学C

先求出x,y的最简比例。然后求出可以扩大的最大比例k,对应的答案就是k*x,k*y。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <math.h>
 5 #include <string.h>
 6 #include <algorithm>
 7 using namespace std;
 8 int a,b,x,y;
 9 int main()
10 {
11     while(scanf("%d%d%d%d",&a,&b,&x,&y)!=EOF)
12     {
13         int ans=__gcd(x,y);
14         x/=ans;
15         y/=ans;
16         int k=min(a/x,b/y);///找出允许的最大比例
17         printf("%d %d
",x*k,y*k);///从最终的比例上扩大倍数
18     }
19     return 0;
20 }

View Code

数学D

求出两个矩形的交点。在交点中可能出现4交点，也可能出现8交点。这个就取决于a的大小，当然我们需要求出一个临界角度，旋转之后矩形的对角线刚好和未旋转的矩形对角线重合。求出角度后再求出点，再加个凸包的面积计算就可以了。(听说还可以用”半平面交”然而我不会)

 1 #include <iostream> 
 2 #include <iomanip> 
 3 #include <stdio.h> 
 4 #include <set> 
 5 #include <vector> 
 6 #include <map> 
 7 #include <cmath> 
 8 #include <algorithm> 
 9 #include <memory.h> 
10 #include <string> 
11 #include <sstream> 
12   
13 using namespace std; 
14   
15 const long double pi = 3.1415926535897932384626433832795; 
16   
17 long double x[42], y[42]; 
18 int n; 
19   
20 void add(int qx, int qy, long double ang) 
21 { 
22     x[n] = cos(ang)*qx-sin(ang)*qy; 
23     y[n] = sin(ang)*qx+cos(ang)*qy; 
24     n++; 
25 } 
26   
27 void cut(long double xa, long double ya, long double xb, long double yb) 
28 { 
29     long double a = yb-ya, b = xa-xb; 
30     long double c = -a*xa-b*ya; 
31     long double eps = (1e-10)*1.00042; 
32     int nn = 0; 
33     long double xx[42], yy[42]; 
34     x[n] = x[0]; 
35     y[n] = y[0]; 
36     for (int i=0; i<n; i++) 
37     { 
38         long double z1 = a*x[i]+b*y[i]+c; 
39         if (z1 < eps) 
40         { 
41             xx[nn] = x[i]; 
42             yy[nn] = y[i]; 
43             nn++; 
44         } 
45         long double z2 = a*x[i+1]+b*y[i+1]+c; 
46         if (z1 < eps && z2 > eps || z1 > eps && z2 < eps) 
47         { 
48             long double aa = y[i+1]-y[i], bb = x[i]-x[i+1]; 
49             long double cc = -aa*x[i]-bb*y[i]; 
50             long double d = a*bb-b*aa; 
51             xx[nn] = (b*cc-c*bb)/d; 
52             yy[nn] = (c*aa-a*cc)/d; 
53             nn++; 
54         } 
55     } 
56     n = nn; 
57     for (int i=0; i<n; i++) x[i] = xx[i], y[i] = yy[i]; 
58 } 
59   
60 int main() 
61 { 
62     //freopen("in.txt","r",stdin); 
63     //freopen("out.txt","w",stdout); 
64     int w, h, iang; 
65     while(scanf("%d %d %d", &w, &h, &iang)!=EOF) 
66     { 
67         long double ang = iang/180.0*pi; 
68         n = 0; 
69         add(w, h, ang); 
70         add(-w, h, ang); 
71         add(-w, -h, ang); 
72         add(w, -h, ang); 
73         cut(w, h, -w, h); 
74         cut(-w, h, -w, -h); 
75         cut(-w, -h, w, -h); 
76         cut(w, -h, w, h); 
77         x[n] = x[0]; 
78         y[n] = y[0]; 
79         long double area = 0; 
80         for (int i=0; i<n; i++) area += (x[i]-x[i+1])*(y[i]+y[i+1]); 
81         printf("%f
", (double)(0.125*area)); 
82     } 
83     return 0; 
84 }

半平面交代码，有兴趣可以看看

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #include <math.h>
  5 #include <string.h>
  6 #include <algorithm>
  7 using namespace std;
  8 const double eps=1e-10;
  9 const double pi=acos(-1.0);
 10 double  w,h,a;
 11 struct Point
 12 {
 13     double x,y;
 14     Point(double x=0,double y=0):x(x),y(y) {}///11?¨¬o¡¥¨ºy
 15 };
 16 Point p[10];
 17 typedef Point VC;
 18 ///向量+向量=向量,点+向量=点
 19 VC operator +(VC A,VC B)
 20 {
 21     return VC(A.x+B.x,A.y+B.y);
 22 }
 23 ///点-点=向量
 24 VC operator -(VC A,VC B)
 25 {
 26     return VC(A.x-B.x,A.y-B.y);
 27 }
 28 ///向量*数=向量
 29 VC operator *(VC A,double p)
 30 {
 31     return VC(A.x*p,A.y*p);
 32 }
 33 ///向量/数=向量
 34 VC operator /(VC A,double p)
 35 {
 36     return VC(A.x/p,A.y/p);
 37 }
 38 double Cross(VC A,VC B)
 39 {
 40     return A.x*B.y-A.y*B.x;
 41 }
 42 double Area2(Point A,Point B,Point C)
 43 {
 44     return Cross(B-A,C-A);
 45 }
 46 VC Rotate(VC A,double rad )
 47 {
 48     return VC(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
 49 }
 50 Point GetLineIntersection(Point P,VC v,Point Q,VC w)
 51 {
 52     VC u=P-Q;
 53     double t=Cross(w,u)/Cross(v,w);
 54     return P+v*t;
 55 }
 56 double ConvexPolygonArea(Point *p,int n)
 57 {
 58     double area=0;
 59     for(int i=1; i<n-1; i++)
 60         area+=Cross(p[i]-p[0],p[i+1]-p[0]);
 61     return area/2;
 62 }
 63 int main()
 64 {
 65     //freopen("in.txt","r",stdin);
 66     //freopen("out2.txt","w",stdout);
 67     while(scanf("%lf%lf%lf",&w,&h,&a)!=EOF)
 68     {
 69 
 70         if(h<w) h=w+h,w=h-w,h=h-w;
 71         int len=0;
 72         if(a==0||a==180)
 73         {
 74             printf("%f
",w*h);
 75             continue;
 76         }
 77         Point A,AA,B,BB,C,CC,D,DD;
 78         if(a>90) a=180-a;
 79         A=Point(h/2,w/2);
 80         AA=Rotate(A,a*pi/180);
 81         B=Point(-h/2,w/2);
 82         BB=Rotate(B,a*pi/180);
 83         C=Point(-h/2,-w/2);
 84         CC=Rotate(C,a*pi/180);
 85         D=Point(h/2,-w/2);
 86         DD=Rotate(D,a*pi/180);
 87         if(a*1.0-2*(atan(1.0*w/h)*180/pi)>0)
 88         {
 89 
 90             Point p1=GetLineIntersection(A,B-A,DD,CC-DD);
 91             Point p2=GetLineIntersection(A,B-A,AA,BB-AA);
 92             Point p3=GetLineIntersection(D,C-D,DD,CC-DD);
 93              printf("%f
",Area2(p1,p2,p3));
 94         }
 95         else if(fabs(a*1.0-2*(atan(1.0*w/h)*180/pi))<eps)
 96         {
 97             printf("%f
",w*h);
 98             continue;
 99         }
100         else
101         {
102             p[0]=GetLineIntersection(A,B-A,AA,DD-AA);
103             p[1]=GetLineIntersection(A,B-A,AA,BB-AA);
104             p[2]=GetLineIntersection(B,C-B,BB,AA-BB);
105             p[3]=GetLineIntersection(B,C-B,BB,CC-BB);
106             p[4]=GetLineIntersection(C,D-C,CC,BB-CC);
107             p[5]=GetLineIntersection(C,D-C,CC,DD-CC);
108             p[6]=GetLineIntersection(D,A-D,DD,CC-DD);
109             p[7]=GetLineIntersection(D,A-D,DD,AA-DD);
110             printf("%f
",ConvexPolygonArea(p,8));
111         }
112     }
113 }

几何代码

数学E

由于n的过大。线性的求法难以忍受。矩阵快速幂+取模(忘记了我就呵呵哒),就可以解决。

http://www.cnblogs.com/vongang/archive/2012/04/01/2429015.html

 1 #include <iostream> 
 2 #include <stdio.h> 
 3 #include <stdlib.h> 
 4 #include <string.h> 
 5 #include <algorithm> 
 6 using namespace std; 
 7 int aa,bb,n,m,mod[]={1,10,100,1000,10000,100000}; 
 8 struct mxt 
 9 { 
10     int v[2][2]; 
11 }ans,temp; 
12 mxt mul(mxt a,mxt b) 
13 { 
14     mxt en; 
15     memset(en.v,0,sizeof(en.v)); 
16     for(int i=0;i<2;i++) 
17         for(int j=0;j<2;j++) 
18         for(int k=0;k<2;k++) 
19         en.v[i][j]=(en.v[i][j]+a.v[i][k]*b.v[k][j])%mod[m]; 
20     return en; 
21 } 
22 mxt pow_mod(mxt a,int k) 
23 { 
24     mxt r; 
25     memset(r.v,0,sizeof(r.v)); 
26     r.v[0][0]=r.v[1][1]=1;
27     while(k) 
28     { 
29         if(k&1) r=mul(r,a); 
30         a=mul(a,a); 
31         k>>=1; 
32     } 
33     return r; 
34 } 
35   
36 int main() 
37 { 
38     int t; 
39     scanf("%d",&t); 
40     while(t--) 
41     { 
42         scanf("%d%d%d%d",&aa,&bb,&n,&m); 
43         if(n==0) printf("%d
",aa%mod[m]); 
44         else if(n==1) printf("%d
",bb%mod[m]); 
45         else
46         { 
47             memset(temp.v,0,sizeof(temp.v)); 
48             temp.v[0][0]=aa; 
49             temp.v[0][1]=bb; 
50             temp.v[1][0]=aa+bb; 
51             temp.v[1][1]=bb; 
52             ans.v[0][0]=ans.v[0][1]=ans.v[1][0]=1;ans.v[1][1]=0; 
53             ans=pow_mod(ans,n-1); 
54             printf("%d
",(ans.v[0][0]*bb+ans.v[0][1]*aa)%mod[m]); 
55         } 
56     } 
57     return 0; 
58 }

View Code

数学F

枚举出四边形的对角线，然后分别在对角线两边(使用叉积判断点在对角线周围的位置)找距离对角线最远的点。要注意对于某一条对角线,如果其他点都在他的一侧的话，就算这个面积再大，也是不能取的

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <math.h>
 5 #include <string.h>
 6 #include <algorithm>
 7 using namespace std;
 8 const int maxn=305;
 9 const double eps=1e-10;
10 const double pi=acos(-1);
11 int  n;
12 struct Point
13 {
14     double x,y;
15     Point(double x=0,double y=0):x(x),y(y) {}///构造函数
16 };
17 Point p[maxn];
18 typedef Point VC;
19 ///向量+向量=向量,点+向量=点
20 VC operator +(VC A,VC B){return VC(A.x+B.x,A.y+B.y);}
21 ///点-点=向量
22 VC operator -(VC A,VC B) {return VC(A.x-B.x,A.y-B.y);}
23 ///向量*数=向量
24 VC operator *(VC A,double p) {return VC(A.x*p,A.y*p);}
25 ///向量/数=向量
26 VC operator /(VC A,double p) {return VC(A.x/p,A.y/p);}
27 double Cross(VC A,VC B){return A.x*B.y-A.y*B.x;}
28 double Dot(VC A,VC B) {return A.x+B.x+A.y*B.y;}///点积=|A|*|B|*cos<A,B>,A，B的逆时针转旋角,满足交换率
29 double length(VC A) {return sqrt(Dot(A,A));}///长度
30 VC Rotate(VC A,double rad)///rad弧度
31 {
32     return VC(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
33 }
34 Point GetLineIntersection(Point P,VC v,Point Q,VC w)
35 {
36     VC u=P-Q;
37     double t=Cross(w,u)/Cross(v,w);
38     return P+v*t;
39 }
40 double DistanceToLine(Point P,Point A,Point B)///p到直线a,b
41 {
42     VC v1=B-A,v2=P-A;
43     return fabs(Cross(v1,v2))/length(v1);///如不取绝对值，得到的是又向距离。
44 }
45 int dcmp(double x)///涉及精度问题
46 {
47     if(fabs(x)<eps) return 0;
48     return x<0?-1:1;
49 }
50 bool OnSegment(Point p,Point a1,Point a2)
51 {
52     return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;
53 }
54 VC vv[maxn*maxn];
55 int main()
56 {
57     //freopen("in.txt","r",stdin);
58     int len=0;
59     while(scanf("%d",&n)!=EOF)
60     {
61         //printf("%d
",n);
62         len=0;
63         for(int i=0;i<n;i++)
64         {
65             scanf("%lf%lf",&p[i].x,&p[i].y);
66         }
67         double  ansmax=0;
68         for(int i=0;i<n;i++)
69         {
70             for(int j=i+1;j<n;j++)
71             {
72                 //vv[len]=VC(p[j]-p[i]);///向量起点为p[i]
73                 double ansmax1,ansmax2,anslength=length(p[j]-p[i]);
74                 //printf("length=%f
",anslength);
75                 ansmax1=ansmax2=0;
76                 for(int k=0;k<n;k++)
77                 {
78                     if(k==i||k==j) continue;
79                     else
80                     {
81                         double ans=Cross(p[j]-p[i],p[k]-p[i]);
82                         if(ans>0) ansmax1=max(ansmax1,DistanceToLine(p[k],p[i],p[j]));
83                         else if(ans<0) ansmax2=max(ansmax2,DistanceToLine(p[k],p[i],p[j]));
84                     }
85                 }
86                 if(ansmax1!=0&&ansmax2!=0)
87                 ansmax=max(ansmax,anslength*(ansmax1+ansmax2)/2);
88             }
89         }
90         printf("%f
",ansmax);
91     }
92 }

拙计的代码

数学G

裸尼姆博弈，答案在必胜态和必败态里面。

http://www.cnblogs.com/kuangbin/archive/2011/08/28/2156426.html

 1 #include <iostream> 
 2 #include <stdio.h> 
 3 #include <stdlib.h> 
 4 #include <algorithm> 
 5 using namespace std; 
 6 int main() 
 7 { 
 8     int t; 
 9     scanf("%d",&t); 
10     while(t--) 
11     { 
12         int n; 
13         scanf("%d",&n); 
14         int flag=0;
15         int s=0; 
16         for(int i=0;i<n;i++) 
17         { 
18             int x; 
19             scanf("%d",&x); 
20             if(i==0) s=x; 
21             else s^=x; 
22             if(x>1) flag=1; 
23         } 
24         if(flag==0) 
25         { 
26             if(n%2==0) {printf("A
");continue;} 
27             printf("B
"); 
28         } 
29         else
30         { 
31             if(s==0) {printf("B
");continue;} 
32             printf("A
"); 
33         } 
34     } 
35     return 0; 
36 }

View Code

数学H

最大值的分布是1,2,….n。分别求出对应的可能数量。比如最大值是k(k>1)，那么以k为最大值的数量有k^n-(k-1)^n.然后我们就可以求出概率了。E=概率*k.对E进行化简就会得出E=m-(1/m)^n-(2/m)^n-…-((m-1)/m)^n

 1 #include<stdio.h> 
 2 #include<math.h> 
 3 int main() 
 4 { 
 5     int n,m; 
 6     double sum; 
 7     while(scanf("%d%d",&m,&n)!=EOF) 
 8     { 
 9         sum=m; 
10         for(int i=1; i<m; i++) 
11         { 
12             sum-=pow((double)1.0-(double)i/m,(double)n); 
13         } 
14         printf("%.12lf
",sum); 
15     } 
16     return 0; 
17 }

View Code