HDU

2011-07-19
[计算几何]HDU_3834 2011多校第一场-HNU

Where am i

这题一开始以为很难,然后直接pass了,后来看到有人写解题报告才70+行的代码,于是决定写这题--||||.写到一半无奈那位朋友的方法不懂,好吧那自己慢慢搞吧[那位朋友貌似用复数搞的,无限ym啊]然后搞了好久一直处于样例不过的状态,而且网上解题报告很少.一直查思路,查代码.一直觉得自己思路是对的[自己当然觉得自己是对的了--||],后来幸运搞到几组数据,然后各种改啊,就过了,下面是思路:

首先可以把打圆平移到和原点重合,然后大圆半径减去小圆半径.再处理其他的.然后小圆变成一个点

1.算出小圆和和大圆第一碰撞所需时间,如果所给时间比这个时间短,直接算,否则进入2

2.算出第一次碰撞的交点,和相应的夹角,假设圆心为0,小圆起始点为A,碰撞点为B,第二次碰撞的交点为C,算出角ABO的大小,然后可以算出BC的长度和所需要的时间,这样就可以了

3.得到上面的信息之后,可以算出经过整数次弦长之后,还剩下多少时间,以及所处的位置和当前的速度方向,然后剩下的就简单了.最后再把大圆的圆心反原回去即可

要注意的是旋转的时候一定要考虑到底是顺时针还是逆时针,我就是因为这个WA了n次!!!

附上代码:



1. /
2. 1.把圆心移到原点
3. 2.大圆的半径减掉小圆的半径
4.
5. !!!用到斜率就要注意 斜率为0的情况!!!
6.
7. 1.角度问题,首先 对acos来说 i和2pi-i是一样的
8. 还有atan2(y,x)得到y/x的正切值,返回值为[-pi,pi]
9. 这里还有一个角度问题就是转的时候可能是顺时针转
10. 也就是角度旋转的时候不是用加了而是用减!!!!!!!
11. 代码中的flag就是用来判断顺时针还是逆时针的
12. 还有一个就是向量旋转的表达式
13. /
14. #include
15. #include
16. #include
17. #include
18.
19. const double eps = 1e-6
20. const double pi = acos(-1.0);
21.
22. typedef struct
23. {
24. double x,y;
25. }TPoint;
26.
27. typedef struct
28. {
29. double x,y,r;
30. }TCircle;
31.
32. TCircle ball,sball;
33. TPoint vec,convert;
34. double T;
35. int flag;
36.
37. inline double squ(double x)
38. {
39. return xx;
40. }
41.
42. double dot(TPoint a,TPoint b,TPoint c)
43. {
44. return (b.x-a.x)(c.x-a.x)+(b.y-a.y)(c.y-a.y);
45. }
46.
47. int cross(TPoint a,TPoint b,TPoint c)
48. {
49. double ret = (b.x-a.x)(c.y-a.y)-(b.y-a.y)(c.x-a.x);
50. if(ret>eps)
51. return 1
52. return -1
53. }
54. void work()
55. {
56. convert.x = ball.x;
57. convert.y = ball.y;
58.
59. sball.x -= convert.x;
60. sball.y -= convert.y;
61. ball.x =0
62. ball.y = 0
63. ball.r -= sball.r;
64.
65. TPoint me = {sball.x,sball.y};
66.
67. if(fabs(vec.x) < eps & fabs(vec.y) < eps)
68. {/vec is zero/
69. me.x += convert.x;
70. me.y += convert.y;
71. printf(“%.1f %.1f\n”,me.x,me.y);
72. return
73. }
74. if(fabs(ball.r)
75. {/sball.r == ball.r/
76. me.x += convert.x;
77. me.y += convert.y;
78. printf(“%.1f %.1f\n”,me.x,me.y);
79. return
80. }
81.
82. if(squ(me.x+Tvec.x)+squ(me.y+Tvec.y)+eps
83. {
84. me.x = me.x+Tvec.x;
85. me.y = me.y+Tvec.y;
86. me.x += convert.x;
87. me.y += convert.y;
88. printf(“%.1f %.1f\n”,me.x,me.y);
89. return ;
90. }
91.
92.
93. double k=vec.y/vec.x;
94. double b=me.y-kme.x;
95. double x1;
96.
97. //printf(“k:%f b:%f %f\n”,k,b,ball.r);
98. if(vec.x<0)
99. {
100. x1=(-kb-sqrt(squ(kball.r)+squ(ball.r)-squ(b)))/(squ(k)+1);
101. }
102. else
103. {
104. x1=(-kb+sqrt(squ(kball.r)+squ(ball.r)-squ(b)))/(squ(k)+1.0);
105. }
106. /fjjjjj/
107. double y1=kx1+b;
108. /
109. x1 & y1
110. /
111. // printf(“(x1,y1)%f %f\n”,x1,y1);
112.
113.
114. TPoint tmp1 = {x1,y1};
115. TPoint tmp2 = {0,0};
116. double u = dot(tmp1,tmp2,me);
117. flag = cross(tmp1,tmp2,me);
118.
119. /
120. flag
121. /
122. //printf(“flag:%d\n”,flag);
123.
124. u = u/(sqrt(squ(x1-me.x)+squ(y1-me.y))ball.r);
125.
126. double l=(u)ball.r;
127. l *= 2
128. u = acos(u);
129.
130. /
131. l
132. /
133. //printf(“l:%f\n”,l);
134.
135.
136. double t1 = l/sqrt(squ(vec.x)+squ(vec.y));
137.
138. __int64 time = (T-(x1-me.x)/vec.x)/t1;
139.
140. /
141. time
142. /
143. //printf(“time:%I64d\n”,time);
144.
145. T = T-(x1-me.x)/vec.x-time*t1;
146.
147. /
148. lefttime
149. */
150. // printf(“lefttime:%f\n”,T);
151.
152.
153. /上面以对 很可能是角度算错了 下面的要仔细验证下!!!/
154. double u2=atan2(y1,x1);
155. double u3 = (time+1)(pi-2u)flag;
156. u2 += time(pi-2u)flag;
157. double x2 = ball.rcos(u2);
158. double y2 = ball.rsin(u2);
159.
160. //printf(“%f %f(x2,y2)\n”,x2,y2);
161. TPoint vec2;
162.
163. vec2.x = vec.xcos(u3)-vec.ysin(u3);
164. vec2.y = vec.xsin(u3)+vec.ycos(u3);
165.
166. me.x = x2+vec2.xT+convert.x;
167. me.y = y2+vec2.y*T+convert.y;
168. printf(“%.1f %.1f\n”,me.x,me.y);
169. return
170. }
171. int main(void)
172. {
173. #ifndef ONLINE_JUDGE
174. freopen(“G.in”,“r”,stdin);
175. freopen(“G.out”,“w”,stdout);
176. #endif
177. int t;
178. scanf(“%d”,t);
179. while(t–)
180. {
181. scanf(“%lf%lf%lf”,ball.x,&ball.y,&ball.r);
182. scanf(“%lf%lf%lf”,sball.x,&sball.y,&sball.r);
183. scanf(“%lf%lf%lf”,vec.x,&vec.y,&T);
184. work();
185. }
186. return 0
187. }

2011-07-03
[树状数组&&逆元]HDU_3074

这题可以用线段树直接做,保存的节点信息是所有的乘积[模上1000000007之后的],不过线段树不好敲,如果有模板的话,还好.没有模板的话,那么少则30分钟吧.

后来才发现原来可以用树状数组+逆元解决这个问题,当然用树状数组和逆元的话,就需要知道两个问题:

1.乘法符合区间可加性

2.a/b%p <====> c*a%p 其中c是b的逆元

这题就是用了这两条性质,这两条性质想清楚之后,这题就好敲了,当然树状数组的更新和求值就会有一点小小的变化.首先对于每个求区间的乘积的问题.我们可以转化成(get(k2)c)%p[get是树状数组的求值函数,(cget(k1-1))%p=1,也就是c是get(k1-1)的逆元]更新也用到逆元,所以增加一个数组来存每个元素.附代码:



1. /
2. 这题首先可以用线段树做,不过写起来比较麻烦
3. 第二个就是用树状数组做,用树状数组做首先要
4. 知道两个问题:
5. 一 乘法符合区间可加性
6. 二 逆元
7. /
8. #include
9. #include
10. #include
11. #include
12.
13. const int max=50006;//最大值
14. const int64 mod=1000000007;//模数
15.
16. int64 tree[max];//树状数组
17. int64 num[max];//原数组
18.
19. int n,q;
20. void init_tree()
21. {//初始化
22. for(int i=0;i
23. tree[i]=1;
24. }
25. void update(int idx,int64 val)
26. {//更新
27. while(idx<=max)
28. {
29. tree[idx] = (tree[idx](val%mod))%mod;
30. idx += idx -idx;
31. }
32. }
33.
34. int64 get(int idx)
35. {//求值
36. int64 ret=1;
37. while(idx>0)
38. {
39. ret = (tree[idx]ret)%mod;
40. idx -= idx -idx;
41. }
42. return ret%mod;
43. }
44.
45. void ex_gcd(int64 a,int64 b,int64 x,int64 &y)
46. {//扩展欧几里得
47. int64 t;
48. if(0 == b)
49. {
50. x = 1;
51. y = 0;
52. return
53. }
54. ex_gcd(b,a%b,x,y);
55. t = x;
56. x = y;
57. y = t - a/b*y;
58. return
59. }
60. int main(void)
61. {
62. #if 1
63. freopen(“3074.in”,“r”,stdin);
64. freopen(“3074.out”,“w”,stdout);
65. #endif
66. int t,tmp;
67. int type;
68. int64 k1,k2;
69. int64 x,y;
70. int64 a,b;
71. scanf(“%d”,t);
72. while(t–)
73. {
74. init_tree();
75. scanf(“%d”,n);
76. for(int i=1;i<=n;i++)
77. {
78. scanf(“%d”,tmp);
79. num[i]=tmp;
80. update(i,tmp);
81. }
82. #if 0
83. for(int i=1;i<=n;i++)
84. printf(“%I64d %I64d\n”,num[i],tree[i]);
85. #endif
86. scanf(“%d”,q);
87. while(q–)
88. {
89. scanf(“%d%I64d%I64d”,type,&k1,&k2);
90. if(1==type)
91. {//change the k1-th num to k2
92. ex_gcd(num[k1],mod,x,y);
93. x = (x%mod+mod)%mod;//这是必须的
94. update(k1,x);
95. update(k1,k2);
96. num[k1]=k2;
97. #if 0
98. printf(“:::x:::%d\n”,x);
99. #endif
100. }
101. else
102. {
103. a=get(k2);
104. b=get(k1-1);
105. ex_gcd(b,mod,x,y);
106. x = (x%mod+mod)%mod;
107. a = ((a%mod)*(x%mod))%mod;
108. printf(“%I64d\n”,a);
109. }
110. }
111. #if 0
112. printf(“=============\n”);
113. for(int i=1;i<=n;i++)
114. printf(“%I64d %I64d\n”,num[i],tree[i]);
115. #endif
116. }
117. return 0;
118. }

2011-05-18
[数论]HDU_2879

传送门

首先给出,He函数是一个积性函数,然后He[p^n]=2,其中p是素数.那么He[n]就是2^k,k是不同素数的个数.那么HeHe[n]函数就是计算所有的n/p,p是素数.那么这题就变成了证明He[n]是素数函数.下面给出一个简单证明,如有错误还请指出:

首先He[p]=2.p是素数. x^2=x(mod p)—->p|x(x-1).因为x<p所以p不整除x也不整除x-1.所以成立的情况下是x=1或者x=0.

He[p^k]=2,证明类似上面的

对于不同的两个素数p和q,He[pq]=4=He[p]He[q];

首先x=0和x=1是肯定成立的,

现在由x^2=x(mod p*q)

   --->p*q|x(x-1)

 假设x=k*p[k<q]

 ------>p*q|k*p(k*p-1)

------->q|k(k*p-1)

——->q|(k*p-1) 因为k<q q是素数 所以gcd(k,q)=1

——->kp+tq=1

这里就变成了这个方程的解,由扩展欧几里得知,这个方程有解,但是k在[0,q-1]之内的解就一个,所以这里多一个解,同理设x=kp又有一个解,所以x^2=x(mod pq)有4个解(x=0 ,x=1 ,x=kp, x=kq)

—->He[pq]=4=He[p]He[q];

那么He[p1^r1p2^r2……*pk^rk]=2^k然后可以进一步算出HeHe只需要算n以内每个素数的倍数的个数.

2011-05-16
[博弈]HDU_2873

传送门
VC时死活过不了的一题,原来是我把题目的输入搞错了,这出题的也太搞了,把读入的第一行的第一个当成(1,1)居然也不表示一下,我表示很蛋疼- -||,一般不都是第一行的最后一个表示(n,m)的么?
VC时,我说:我保证sg函数没错,然后我保证是这样搞的,然后就没有然后了,就一直死活过不了,后来找了报告,发现看不懂他的代码,不过思想也是博弈SG函数.然后作死的调啊调.可能是上天可怜我了,给我一组数据,而且我对拍是发现不对,最最重要的是,发现了那个正确的读入和我的不同啊@@@@@@.我想死啊.尼玛就不能说明下啊.
下面是说明,对于SG函数,sg[i]=mex{n,i可到n},mex是集合中未出现的最小值(>=0).然后对于对个SG游戏的当前局面就是当前所有点的sg函数的异或,这个Game Theory上有证明,自己去看去.然后就没有然后了,这题就变成水题了.代码:



1. #include
2. #include
3. #include
4. #include
5. int sg[56][56];
6. int n,m;
7. void init_sg()
8. {
9. int i,j;
10. int used[5151];
11. int ii,jj;
12. for(i=1i<56;i++)
13. {
14. sg[i][1]=i-1
15. sg[1][i]=i-1
16. }
17. for(i=2i<51;i++)
18. {
19. for(j=2j<51;j++)
20. {
21. memset(used,0,sizeof(used));
22. for(ii=1ii
23. {
24. for(jj=1jj
25. {
26. used[sg[ii][j]^sg[i][jj]]=1
27. }
28. }
29. for(ii=0ii<2501;ii++)
30. {
31. if(0 == used[ii])
32. {
33. sg[i][j]=ii;
34. break
35. }
36. }
37. }
38. }
39. #if 0
40. printf(“:::::::::::::::::::\n”);
41. for(i=1i<6;i++)
42. {
43. for(j=1j<6;j++)
44. printf(“%d “,sg[i][j]);
45. printf(“\n”);
46. }
47. printf(“:::::::::::::::::::\n”);
48. #endif
49. }
50. void work()
51. {
52. int i,j;
53. char c;
54. int ans=0
55. for(i=1i<=n;i++)
56. {
57. for(j=1j<=m;j++)
58. {
59. scanf(“%c”,c);
60. if(‘#’ == c)
61. {
62. ans ^= sg[i][j];
63. }
64. }
65. getchar();
66. }
67. if(0 == ans)
68. printf(“Jack\n”);
69. else
70. printf(“John\n”);
71. return ;
72. }
73. int main(void)
74. {
75. freopen(“2873.in”,“r”,stdin);
76. freopen(“2873.out”,“w”,stdout);
77. init_sg();
78. while(1)
79. {
80. scanf(“%d%d%c”,n,&m);
81. if(0 == n & 0==m)
82. break
83. work();
84. }
85. return 0
86. }

2011-05-13
因子个数_HDU_1299

这题就是要求1/x+1/y=1/n,给出n,算出满足条件的x,y对(x<=y).首先我们知道x和y都是大于n的,x<=2n,现在我们假设x=n+k(0<k<=n),那么y=n+n^2/k,我们知道y是整数,所以n^2一定是k的倍数,也就是k|n^2.这就要求我们求n^2的因子数了,OK,不过好像k还有限制条件- -|,其实我们可以先不考虑这个条件,因为x和y是对称的,所以算出总结过ans之后,ans’=(ans+1)>>1就是了.(加1是因为1/2n+1/2n=1/n这个式子只会出现一次).现在这题就变成了求一个数的因子数,我求因子数还是先分解素数做的,由于n^2实在太大,求sqrt(n^2)=n以内的素数也不可实现.其实我们只需要求出n的因子分解就行了,因为n^2=nn,那么因子的次方就是n的因子分解之后每个素数次方的2倍.这样这题就解决了,下面是代码:



1. #include
2. #include
3. #include
4. #include
5. const int MAX_N=6666;
6. int prime[MAX_N],idx;
7. int n;
8. void init_prime()
9. {
10. int i,j;
11. char p= (char )malloc(sizeof(char)65546);
12. memset(p,0,sizeof(char)65546);
13. for(i=2;i<65536;i+=2) <="" span="">
14. p[i]=1;
15. prime[0]=2;
16. idx=1;
17. for(i=3;i<65536;i+=2) <="" span="">
18. {
19. if(0 == p[i])
20. {
21. prime[idx]=i;
22. idx++;
23. if(i<257) <="" span="">
24. {/注意这里ii可能会越界/
25. for(j=ii;j<65536;j +="2*i)" <="" span="">
26. {
27. p[j]=1;
28. }
29. }
30. }
31. }
32. free(p);
33. }
34. void work()
35. {
36. int ans=1;
37. int i,j;
38. for(i=0;i
39. {
40. if(0 == (n%prime[i]))
41. {
42. j = 0;
43. while(0 == (n%prime[i]))
44. {
45. j++;
46. n /= prime[i];
47. }
48. ans = (2j+1);
49. }
50. if(1 == n)
51. {
52. break
53. }
54. }
55. if(n>1)
56. {
57. ans *= 3;
58. }
59. ans = (ans+1)>>1;
60. printf(“%d\n\n”,ans);
61. }
62. int main(void)
63. {
64. int t,i;
65. init_prime();
66. scanf(“%d”,t);
67. for(i=1;i<=t;i++)
68. {
69. scanf(“%d”,n);
70. printf(“Scenario #%d:\n”,i);
71. work();
72. }
73. return 0;
74. }

2011-05-05
HDU_2857_计算几何

这题就是一个反射的题,给出光源和反射之后的一个点,输出反射点.VC时我一直用高中的方法去搞,而且没有考虑特殊情况,导致浪费了很多时间.回来就搜了下,发现这题基本就是一系列模板套上去就OK了,首先是点关于直线的对称点,然后是两条直线的交点,OK手工.下面给出我的代码:



1. #include
2. #include
3. #include
4. #include
5.
6. typedef struct
7. {
8. double x,y;
9. }TPoint;
10.
11. typedef struct
12. {
13. double a,b,c;
14. }TLine;
15.
16. TPoint src,end,sym,ref;
17. TPoint mirr_point[2];
18. TLine mirr;
19. /通过直线上的两个点得到直线的一般式/
20. TLine get_line(TPoint p1,TPoint p2)
21. {
22. TLine ret;
23. ret.a = p1.y-p2.y;
24. ret.b = p2.x-p1.x;
25. ret.c = p1.xp2.y-p2.xp1.y;
26. return ret;
27. }
28. /返回一个数的平方/
29. double squ(double a)
30. {
31. return aa;
32. }
33. /得到p关于l的对称点/
34. TPoint symmetric_point(TPoint p,TLine l)
35. {
36. TPoint ret;
37. double d = squ(l.a)+squ(l.b);
38. ret.x = (squ(l.b)p.x-squ(l.a)p.x-2l.al.bp.y-2l.al.c)/d;
39. ret.y = (squ(l.a)p.y-squ(l.b)p.y-2l.al.bp.x-2l.bl.c)/d;
40. return ret;
41. }
42. /返回和<p1,p3>的叉积/
43. double cross(TPoint p1,TPoint p2,TPoint p3)
44. {
45. return (p2.x-p1.x)(p3.y-p1.y)-(p2.y-p1.y)(p3.x-p1.x);
46. }
47.
48. /用叉积得到两条直线的交点[前提是直线规范相交]/
49. void work()
50. {
51. /求直线 和<c,d>的交点p的方法
52. 首先是得到4个叉积
53. s1 = cross(a,b,c);
54. s2 = cross(a,b,d);
55. s3 = cross(c,d,a);
56. s4 = cross(c,d,b);
57. p.x = (c.xs2-d.xs1)/(s2-s1);
58. p.y = (s.ys2-d.ys1)/(s2-s1);
59. 推导用定比分点
60. /
61. double s1,s2,s3,s4;
62. s1 = cross(end,sym,mirr_point[0]);
63. s2 = cross(end,sym,mirr_point[1]);
64. s3 = cross(mirr_point[0],mirr_point[1],end);
65. s4 = cross(mirr_point[0],mirr_point[1],sym);
66. ref.x = (mirr_point[0].xs2-mirr_point[1].xs1)/(s2-s1);
67. ref.y = (mirr_point[0].ys2-mirr_point[1].y*s1)/(s2-s1);
68. printf(“%.3f %.3f\n”,ref.x,ref.y);
69. return ;
70. }
71.
72. int main(void)
73. {
74. int t;
75. scanf(“%d”,t);
76. while(t–)
77. {
78. scanf(“%lf%lf”,mirr_point[0].x,&mirr_point[0].y);
79. scanf(“%lf%lf”,mirr_point[1].x,&mirr_point[1].y);
80. scanf(“%lf%lf”,src.x,&src.y);
81. scanf(“%lf%lf”,end.x,&end.y);
82. mirr = get_line(mirr_point[0],mirr_point[1]);
83. sym = symmetric_point(src,mirr);
84. work();
85. }
86. return 0;
87. }

2011-04-19
HDU 3307 欧拉函数

这题首先可以把a(n)的公式推出来,a(n)=x^na(0)+Y(x^n-1)/(x-1).然后a(n)%a(0)=0也就是[x^na(0)+Y(x^n-1)/(x-1)]%a(0)=0那么x^na(0)这一项省略得到Y(x^n-1)/(x-1)%a(0)=0.我们设k=Y/(x-1).因为题中保证(x-1)|Y.所以k是整数.这样就得到k(x^n-1)=0(mod a(0)).也就是k(x^n-1)=m*a(0),其中m>=0且是整数.两边同时除掉gcd(k,a(0))之后就变成了(x^n-1)=0(mod a(0)).也就是x^n=1(mod a(0))[现在的a(0)是原来的a(0)/gcd(a(0),k)].我们知道如果gcd(x,a(0))==1那么x^phi(a(0))=1(mod a(0)).如果不等于1就无解.但是当gcd(x,a(0))=1的时候是不是Phi(a(0))就是题目的答案呢?显然不是,就想4^4=1(mod 5)但是4^2=1(mod 5).但是我们知道如果对于一个数t,x^t=1(mod a(0))的话,那么t|phi(a(0)).这样我们就好办了.只需要枚举phi(a(0))的所有因子就OK了,然后取最小的那个使得x^t=1(moid a(0))的因子就是本题答案了.代码如下:



1. /
2. ID:klion26
3. LANG:C
4. TASK:HDU_3307
5. /
6. #include
7. #include
8. #include
9. #include
10.
11. int64 eular[66000];
12. int64 idx,prime[6600];
13. int64 x,y,a0;
14. int64 total,num[16][2];
15. int64 min;
16. void init()
17. {
18. int64 i,j;
19. int64 n=65536;
20. memset(eular,0,sizeof(eular));
21. eular[1]=1;
22. for(i=2;i<=n;i++)
23. {
24. if(0==eular[i])
25. {
26. prime[idx]=i;
27. idx++;
28. for(j=i;j<=n;j+=i)
29. {
30. if(0 == eular[j])
31. eular[j]=j;
32. eular[j] /= i;
33. eular[j] *= (i-1);
34. }
35. }
36. }
37. }
38. int64 get_eular(int64 n)
39. {
40. int64 ret;
41. int64 i,k;
42. if(n<=65536)
43. return eular[n];
44. for(i=0;i
45. {
46. if(0 == (n%prime[i]))
47. break
48. }
49. if(i == idx)
50. return n-1;
51. k = n/prime[i];
52. if(0 == (k%prime[i]))
53. ret = prime[i]get_eular(k);
54. else
55. ret = (prime[i]-1)get_eular(k);
56. return ret;
57. }
58. int64 gcd(int64 a,int64 b)
59. {
60. int tmp;
61. if(a < b)
62. {
63. tmp = a;
64. a = b;
65. b = tmp;
66. }
67. while(b)
68. {
69. tmp = a;
70. a = b;
71. b = tmp%b;
72. }
73. return a;
74. }
75. int64 pow_mod(int64 a,int64 b,int64 c)
76. {
77. int64 ret = 1;
78. a %= c;
79. while(b)
80. {
81. if(b1)
82. {
83. ret = (reta)%c;
84. }
85. b >>= 1;
86. a = (aa)%c;
87. }
88. return ret;
89. }
90. void dfs(int64 now,int64 level)
91. {
92. int64 i,j;
93. if(level == total)
94. {
95. if((1 == pow_mod(x,now,a0)))
96. {
97. if(now < min)
98. {
99. min = now;
100. }
101. }
102. return ;
103. }
104. j = 1;
105. for(i=0;i<=num[level][1];i++)
106. {
107. now = j;
108. dfs(now,level+1);
109. now /= j;
110. j = num[level][0];
111. }
112. }
113. void work()
114. {
115. __int64 en,i,j;
116. j = y/(x-1);
117. i = gcd(j,a0);
118. a0 /= i;
119. if(1 != gcd(a0,x))
120. {
121. printf(“Impossible!\n”);
122. return ;
123. }
124. en=get_eular(a0);
125. total=0;
126. min = en;
127. for(i=0;i
128. {
129. if(0 == (en%prime[i]))
130. {
131. num[total][0]=prime[i];
132. j=0;
133. while(0 == (en%prime[i]))
134. {
135. j++;
136. en /= prime[i];
137. }
138. num[total][1] = j;
139. total++;
140. }
141. if(1 == en)
142. break
143. }
144. if(en > 1)
145. {
146. num[total][0]=en;
147. num[total][1] = 1;
148. total++;
149. }
150. dfs(1,0);
151. printf(“%I64d\n”,min);
152. }
153. int main(void)
154. {
155. init();
156. while(EOF != scanf(“%I64d%I64d%I64d”,x,&y,&a0))
157. {
158. if(0 == y)
159. printf(“1\n”);
160. else
161. work();
162. }
163. return 0;
164. }

2011-03-24
HDU 3389

首先你可以枚举前几个,然后可以看出分成了三个完全不相干的游戏,[1-2-7-8-13……][3-6-9-12-15……][4-5-10-11……],然后接下来你会发现2可以到1,7可以到2,8可以到7和1,6可以到3,12可以到3和9,5可以到4,11可以到10和4,也就是说如果n%3==0的话,那么如果n是偶数,就可以转移到奇数上,其他的是如果n%3==2的话,那么一定可以转移到n%3==1上,然后我们可以知道最后结果只与n%3==0&n%2==0的位置上的和n%3==2上的数确定,那么我们把上面这两个设置设为集合A,其他的放在B集合,那么如果现在的局势是败局的话,玩家可以移动A集合里面的使之到一个胜局,或者移动B集合里面的东西到A集合,到达一个胜局,如果是从B移过来的,那么接下来的玩家只需要移走这些就行了,如果是从A中移走的话,那么我们继续移走A中的一部分,使之到一个败局.如果是胜局的话,只需要从A集合移动一些数到B集合就OK了,然后接下来的玩家就面临败局了.也就是这题的结果只与n%3==0&&n%2==0和n%3==2的位置上的card数有关

2011-03-15
HDU 1730 博弈

这题首先可以这样想,如果每行的两颗棋子都挨着的话,那么先手就必输,这个好想.那么我们就可以让它变成所有的都挨着,能的话,就能赢,否则就必输[前提是两个人都是按照对自己最有利的形式移动].那么这样就变成了n堆得石子问题了,这里n是行数.这样就简单很多了,只需要算出每行的棋子间距,然后所有的间距异或一下,如果是0的话就是P-position否则是N-position,其中P-position的话先手必输N-position的话先手必赢.至于为什么先手必输或必赢.以前写过一点,等过段时间转到这个博客来.也可以自己参考相应书籍.下面是这题的代码:

/
ID:klion26
TASK:HDU_1730
LANG:C
*/

#include
#include
#include
#include

int main(void)
{
freopen(“hdu-1730.in”,“r”,stdin);
freopen(“hdu-1730.out”,“w”,stdout);
int n,m
int a,b,i,t,k
while(EOF != scanf(“%d%d”,n,&m))
{
t=0
for(i=0i<n;i++)
{
scanf(“%d%d”,a,&b);
k=a>b?a-b-1:b-a-1;//算间距
t ^= k//异或算结果
}
if(0!=t)//N-position
printf(“I WIN!\n“);
else//P-position
printf(“BAD LUCK!\n“);
}
return 0
}
▲