2014/3/2 zoj 3月份月赛/长沙多校第一次

时间2014/3/3

zoj3758 生成指定的一个大数字，并判断是否是素数

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <vector>
 6 #include <queue>
 7 #include <algorithm>
 8 #include <stack>
 9 #include <set>
10 #include <cstdlib>
11 #define LL long long
12 #define ULL unsigned long long
13 #define maxn 2100
14 using namespace std;
15 
16 ULL M[17][17];
17 void init()
18 {
19     for(int i=2;i<=16;i++)
20     {
21         ULL t=1;
22         M[i][0]=t;
23         for(int j=1;j<=16;j++)
24         {
25             t=t*(ULL)i;
26             M[i][j]=t;
27         }
28     }
29     return ;
30 }
31 ULL mult(ULL a,ULL b,ULL n)// a*b % n
32 {
33     ULL s=0;
34     while(b){
35         if(b&1)s=(s+a)%n;
36         a<<=1;b>>=1;
37         if(a>n)a=a%n;
38     }
39     return s;
40 }
41 ULL miller_rabin(ULL n,ULL i)//素数测定，错误机率为1/4
42 {
43     ULL j,k,b=0,a=1;
44     j=n/(1<<i);
45     while(b%n==0)b=abs(rand())%n;
46     while(j)
47     {
48         if(j&1)a=mult(a,b,n);
49         b=mult(b,b,n);j>>=1;
50     }
51     for(k=1;k<=i;k++){
52         if(k<i-1&&mult(a,a,n)==1&&a!=1&&a!=n-1)return 0;
53         a=mult(a,a,n);
54     }
55     if(a==1)return 1;
56     return 0;
57 }
58 ULL prime(ULL n)
59 {
60     ULL m,k,i,s=1;
61     if(n==1)return 0;
62     for(k=0,m=n-1;m%2==0;m/=2,k++);
63     for(i=0,s=1;i<10;i++)s*=miller_rabin(n,k);//调整调用次数
64     return s;
65 }
66 int b,n;
67 int main()
68 {
69     init();
70     while(cin>>b>>n)
71     {
72         ULL num=0;
73         for(int i=0;i<n;i++)
74         num+=M[b][i];
75         if (prime(num)) cout<<"YES"<<endl;else cout<<"NO"<<endl;
76     }
77     return 0;
78 }

View Code

zoj3761 连通分量形成生成树

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <vector>
  6 #include <queue>
  7 #include <algorithm>
  8 #include <stack>
  9 #include <set>
 10 #include <cstdlib>
 11 #define maxn 2100
 12 using namespace std;
 13 
 14 int n,cnt;
 15 int r[maxn];//根结点的编号
 16 vector<int>G[maxn];
 17 struct Point
 18 {
 19     int x,y;
 20 }P[maxn];
 21 int findx(int x)
 22 {
 23     return r[x]==x?x:r[x]=findx(r[x]);
 24 }
 25 void merge(int v,int u)//将v的根节点设置为u
 26 {
 27     int rv=findx(v);
 28     int ru=findx(u);
 29     r[rv]=ru;
 30 }
 31 int yidong(int i,int j)//判断两点的相同的坐标
 32 {
 33     int x1=P[i].x,y1=P[i].y;
 34     int x2=P[j].x,y2=P[j].y;
 35     if (x1==x2 || y1==y2) return 1;else return 0;
 36 }
 37 void doit(int c,int f)//将c点移动到f点
 38 {
 39     int x1=P[c].x,y1=P[c].y;
 40     int x2=P[f].x,y2=P[f].y;
 41     printf("(%d, %d) ",x1,y1);
 42     if (x1==x2)
 43     {
 44         if (y1<y2) cout<<"UP"<<endl;
 45         if (y1>y2) cout<<"DOWN"<<endl;
 46     }
 47     if (y1==y2)
 48     {
 49         if (x1<x2) cout<<"RIGHT"<<endl;
 50         if (x1>x2) cout<<"LEFT"<<endl;
 51     }
 52     return;
 53 }
 54 bool mark[maxn];//标记dfs的节点
 55 void dfs(int st)
 56 {
 57     mark[st]=true;
 58     for(int i=0;i<G[st].size();i++)//递归出口是size==0
 59     {
 60         int v=G[st][i];
 61         if (mark[v]) continue;
 62         dfs(v);
 63         doit(v,st);
 64     }
 65     return ;
 66 }
 67 void solve()
 68 {
 69     int ans=0;
 70     for(int i=1; i<=n; i++) if (i==r[i]) ans++;
 71     cout<<ans<<endl;//找到树的棵树
 72 
 73     memset(mark,0,sizeof(mark));
 74     for(int i=1;i<=n; i++) if (i==r[i]) dfs(i);//每次从根节点dfs下去
 75 }
 76 int main()
 77 {
 78 //    freopen("out.txt","w",stdout);
 79     while(cin>>n)
 80     {
 81         cnt=0;
 82         for(int i=1; i<=n; i++) r[i]=i;
 83         for(int i=1; i<=n; i++)
 84         {
 85             G[i].clear();
 86             cin>>P[i].x>>P[i].y;
 87         }
 88         for(int i=2; i<=n; i++)//枚举出两两之间的连边
 89         {
 90             for(int j=1; j<i; j++)
 91             {
 92                 if (yidong(i,j)==1)//可以移动返回1
 93                 {
 94                     G[i].push_back(j);
 95                     G[j].push_back(i);
 96                     merge(i,j);
 97                 }
 98             }
 99         }
100         solve();
101     }
102     return 0;
103 }

View Code

zoj3759

  1 //zoj3759
  2 //http://www.bingfengsa.com/info/18001.html
  3 //学习笔记(仅仅是填充学习博文中的知识点而以)
  4 /*
  5 【题目要求】：
  6 找到：x(x+1)/2=ky^2      -x^2-x+2ky^2=0          (2x+1)^2-8k*y^2=1
  7       x^2=ky^2           x^2-ky^2=0;              特殊
  8       x(3x-1)/2=ky^2     3x^2-x-2ky^2=0         （6x-1)^2-24ky^2=1
  9       x(2x-1)=ky^2       2x^2-x-2ky^2=0          (4x-1)^2-8y^2=1
 10       x=ky^2             0x^2-x+ky^2=0;          特殊
 11 右边是统一化成的z^2-ny^2=0的形式,z代换了x
 12 
 13 【换元】：z^2-ny^2=1
 14 【佩尔方程】：
 15 显然这个方程有正整数解，则x，y才可能有整数解，
 16 ///////佩尔方程的知识/////////
 17 一、下面的不定方程称为佩尔（Pell）方程：
 18 x^2 - ny^2= 1  设n是正整数
 19 如果d是完全平方数，那么只有平凡解(-1,0),(1,0)
 20 如果不是，一定有无穷多组正整数解
 21 二、递归解：
 22 x[i+1]=x[1]*x[i]+n*y[1]*y[i]
 23 y[i+1]=x[1]*y[i]+y[1]*x[i]
 24 三、基本解(x1,y1)：
 25 首先根据根号n的渐进连分数（h/k)表示，找出前几项，察看x=h,y=k带入后是否是一组解。
 26 是，则得到了(x1,y1)
 27 四、渐进连分数的生成（如截图）：
 28 五、佩尔方程的解是指数增长的（很少）
 29 六、佩尔方程最小解的生成
 30 from : http://blog.csdn.net/accelerator_916852/article/details/20411727
 31 bool pell( int D, int& x, int& y ) {//D就是上文的N
 32     int sqrtD = sqrt(D + 0.0);//这里应该处理精度才行
 33     if( sqrtD * sqrtD == D ) return false;
 34     int c = sqrtD, q = D - c * c, a = (c + sqrtD) / q;
 35     int step = 0;
 36     int X[] = { 1, sqrtD };
 37     int Y[] = { 0, 1 };
 38     while( true ) {
 39         X[step] = a * X[step^1] + X[step];
 40         Y[step] = a * Y[step^1] + Y[step];
 41         c = a * q - c;
 42         q = (D - c * c) / q;
 43         a = (c + sqrtD) / q;
 44         step ^= 1;
 45         if( c == sqrtD && q == 1 && step ) {
 46             x = X[0], y = Y[0];
 47             return true;
 48         }
 49     }
 50 }
 51 ///////佩尔方程的知识/////////
 52 【继续】 现在我们找到了z1，y1，能得到所有的z[i],y[i],现在我们通过这些解，找到最小的x、y正整数解就可以了
 53 【特殊方程的解决】：(题目没要求计算)
 54  1、x^2-ky^2=0;k判断k是否是完全平方数即可
 55  2、0x^2-x+ky^2=0;直接解出x即可
 56  */
 57 
 58 #include<iostream>
 59 #include<string.h>
 60 #include<stdio.h>
 61 #include<stdlib.h>
 62 #include<cmath>
 63 #include<algorithm>
 64 #include<queue>
 65 #include<stack>
 66 #include<set>
 67 #include<map>
 68 #define LL unsigned long long
 69 #define maxn 510
 70 #define INF 99999
 71 using namespace std;
 72 
 73 int k,kind;
 74 
 75 bool pell( int D, LL& x, LL& y ) {//D就是上文的N
 76     LL sqrtD = (LL)sqrt(D + 0.0);//这里应该处理精度才行
 77     if( sqrtD * sqrtD == D || (sqrtD+1) * (sqrtD+1)==D ) return false;
 78     LL c = sqrtD, q = D - c * c, a = (c + sqrtD) / q;
 79     LL step = 0;
 80     LL X[] = { 1, sqrtD };
 81     LL Y[] = { 0, 1 };
 82     while( true ) {
 83         X[step] = a * X[step^1] + X[step];
 84         Y[step] = a * Y[step^1] + Y[step];
 85         c = a * q - c;
 86         q = (D - c * c) / q;
 87         a = (c + sqrtD) / q;
 88         step ^= 1;
 89         if( c == sqrtD && q == 1 && step ) {
 90             x = X[0], y = Y[0];
 91             return true;
 92         }
 93     }
 94 }
 95 
 96 void solve(int N,int a,int b)//写成x=(z+a)/b的形式
 97 {
 98     LL z1,y1;
 99 //    int zi,yi;
100     LL ansx,ansy;
101     bool ok=pell(N,z1,y1);
102     if (!ok)
103     {
104         printf("Impossible!
");
105         return ;
106     }
107     if ((z1+a)%b==0) {ansx=(z1+a)/b,ansy=y1;cout<<ansx<<" "<<ansy<<endl;}
108     else printf("Impossible!
");
109 }
110 int main()
111 {
112     while(cin>>kind)
113     {
114         if (kind==0) break;
115         cin>>k;
116         if (kind==3) solve(8*k,-1,2);
117         else if (kind==5) solve(24*k,1,6);
118         else if (kind==6) solve(8*k,1,4);
119     }
120     return 0;
121 }

View Code