在这战斗的岁月里

其实还是很憋屈。。。。。。lv1那个傻逼题才177多分。。。。。lv2本来可以做到300+的，傻不愣蹬的不会用substr。。。。

大家枪毙我吧。。。。。不过rating还是涨了100+

下次就没那么爽了。。。900进300.。。都是真的干了。。。

还要练习一阵子~~~加油！！！！coding力有待提高。。。。

题目意思是给定m,n问你 m/n的二进制数的最大循环节开始位置和长度。

其实很容易就是判定是否存在 b, l　使得： m*2^b = m*2^b*2^l (mod n) 两边消去m *2^b 
就是求 2^l=1(mod n)

懂的数论的话就知道这个是在求Dn(2) 而这个是无法直接求的，但我们有一些途径可以使得这个比较好求。
有定理1. Dn(a) = [ Dn1(a), Dn2(a).. ] iff n=n1*n2..证明这里略，这个的应用就是 如果n不是prime的话我们就把它分解成这个样子
当然如果含有2的因子这里都忽略，为什么等等说，然后我们的n就标致为 
                n=p1^t1 * p2^t2 *..*pk*tk
在根据定理1我们就转成求 Dn(2) n=p^t 
这时候我们还有定理二. Dn(a) = d iff d | phi(n)
because x^phi(n)=1(mod n) 【欧拉定理】
所以答案肯定是phi(p^t)的一个因子 对于某个p^t而言。
所以我们要做的就是找出所有 p^t(p-1)/p 的因子。
这个咋搞呢，我的实现是对于每个因子都记录下来，然后dfs到一个因子再判定是不是存在可行因子。
然后在求lcd。。好像很麻烦。。。。

不知道还有没有更好的方法。

 

昨天的比赛说实话灰常灰常的郁闷。一开始就被卡还是被自己的模板给卡死了。非常straight的题目就是求凸包。。然后我的模板就自己挂掉了。。后来发现是因为以前写的偷懒。sort以后两边扫描的，结果昨天的卡到死。其实就按极角序一遍扫描就好了。唉看来彪悍的人生不仅需要模板，还需要好的模板啊。。。。

然后就是几道简单题很快过去了。没嘛悬念。接下来两道数论题。。。刚刚好是我没怎么看的指数原根部分的。。。。（高斯二次那个没怎么想）。。。。。。。。。。。然后我的思维再次飘逸了一把。。。。。。。不过没飘逸对。。。。。。。。居居然飘出一个。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。朴素加速来搞。。。。。。。。。。。。。。。。。

接着就比较恶心了先来个map的，当然不行拉，自己写个hash，快多了但是很多数据还是卡死。。。。。。。。。郁闷
比赛结束我才突然想到靠整个operation的个数都超过可接受范围了再快每次查询有蛋用啊！！直接傻逼掉了。。。以后大家切记这个。

然后只好硬着头皮硬搞了。。搞到刚才才把那题搞出来（poj3358不错的数论题 大家有时间都去做做）

晚上我想了想其实这次比赛的最大问题不应该说是我的模板不好或者我刚好数论那块空白，应该说是我的策略有问题，我觉得这个才是最重要的，这个问题同样也是我们都应该思考的。不错，对问题的专研精神是可贵的，但也应该看时候啊，以前听说acrush他们都是比赛的时候3次no的话哪怕离答案再近都要换题，我想这也是个不错的经验，其实如果实力差点我觉得5次都是可以接受的，但是最怕死磕，我的经验是一死磕就毫无悬念了，几乎每次死磕都没好下场。。。。。要是一个队里两个人都开始死磕了。。那准备郁闷吧。。。。除非手头真的没题可以做了。


最后讲下昨天那道mvp吧， 现在我算是对指数问题有了进一步的理解了，关键是你转换成 2^t=1(mod m)就OK 了，然后只要数论合格爱怎么搞怎么搞。。。我就算了。。。。。。。。。。。。。。。。。。。。。。。。。。。。

困了睡觉了。。明天补一篇。。。