richard-desktop

int[] inv = new int[MAXN];
inv[1] = 1;
for (int i = 2; i<MAXN; i++)
    inv[i] = inv[MOD%i]*(MOD-MOD/i)%MOD;

注意这里的MOD必须是素数。

摘自TopCoder上某人的代码。

杭州赛区我们基本上没有犯什么严重的错误，但是反映了一个问题：代码速度太慢。个人觉得这次杭州的题目出的不错，不像Tianjin那样容易变得没有梯度，也不想Harbin那样只有2道难题。这次比赛一共有6道相对简单的题目，剩下的题目都是需要一定时间去做的。

比赛流程还是老样子，我全程都在读题，讲解题目意思。肖刘看完J之后觉得可以写，而我有没有发现什么一下子就可以写的题目，于是就让肖刘先写了。肖刘不负众望，1Y，这种递推、DP的题目肖刘还是很擅长的。然后我们讨论了一下所有题目的意思，觉得还是先写C和H，我轻松1Y了C，李晔晨也1Y了H。这时候已经有队伍4道题了。我们选择了跟一下题目，于是目前可以做的题目就是D、F。我们先写了F，WA了1次之后AC了。然后我们讨论了一下B，觉得是可以做的，于是就上去写，虽然中间犯了很多错误，但是还是AC了。接着我又和肖刘想出了D的算法，最后成功AC。期间李晔晨一直在调试E，未果。

本次比赛比较可惜的是，我们会G的算法，但是没有时间写了。而且I的算法也只差一点就想到了。时间不够用的原因就是代码能力不够，希望以后可以加强这方面的能力，再接再厉。

天津赛区我们发挥得很不好，一方面是实力不够，但是更多的表现为考场上配合问题。比赛的时候依然是我负责看题，看完之后，没有发现任何非常简单的题目。最终我选择了先做E这一个算是比较简单的题目，虽然因为两个小错误WA了2次，但是还算是过得比较快。写完E之后，我给李晔晨和肖刘讲了一下A、B、C、D和I都是可以做的。事实证明，果然也只有这几道是比较好做的。我们想了一会D，然后发现不会做，于是就先写A，肖刘写了很久之后终于写过了，然后开始写D。D这种递推的题目肖刘一直都很擅长，所以选择继续让他写，果然不负众望，成功1Y。接着本次比赛的败笔出现了，李晔晨想出了I的正确算法，但是选择让肖刘实现，而肖刘不是很明白李晔晨的意思，导致各种不停的WA，李晔晨一直在想B和G，所以没有很好的解释清楚。直到最后WA的实在不行了，我让李晔晨上去写，结果迅速1Y。这时候比赛还有1个多小时，我开始写B。由于算法想得很仓促，出现了很多比较难写的情况，最后都没有成功Debug。

天津我们最后以5题收场，说实话这是一个不令人满意的结果。本次比赛问题主要是李晔晨想出了算法的题目都选择让我和肖刘实现，但是这样有时候会有些思维混乱。因此我们赛后总结，如果算法不是那种通用的类型，谁想出算法就是谁写。

热身赛前一天晚上我和李晔晨在房间里面写Java的BigInteger类，以防第二天出现这种类型的题目。但是李晔晨写了一个程序一直RE，我不是很清楚其中的原因，然后看看已经1:30了，就直接睡觉了。

热身赛没什么特别的，我们做了基本上所有的试验，然后没有什么问题。唯一比较好玩的是清华的三个队伍座位都在我们前面，PKU的另外两个队伍也是如此，这样我们比赛的时候观察形势就容易了一点，不过第二天的比赛中长时间的卡题证明了这个座位几乎没起到什么作用。

正式比赛的那一天我感觉有点疲倦，可能是和我的生物钟不太一致，所以现场的状态一直不是很好。以后考虑是不是比赛的时候带点能够提神的东西。开始之后，我一如既往地先去找容易题给肖刘秒杀。结果反而是李晔晨先找到了一个F题AC了，这个时候我已经读题到E，就告诉肖刘ABE可做之后接着去看GHIJ。肖刘先想出了A，就先写了A。这时候脑残的事情发生了，我和李晔晨讨论之后发现B是一个“最大权匹配”，于是李晔晨上去拍了一个网络流的模板，TLE了。我们分析之后认为需要KM算法，但是由于A没写完，就暂时去想题了，期间我告诉李晔晨H的做法，李晔晨表示可以直接模板秒杀，然后就去研究GIJ。J被认为是可以做的，李晔晨就去推导I，我在帮肖刘调试A。A经过一系列的Debug之后终于AC了，然后李晔晨AC了H，继续去想I。关于I，李晔晨曾经有过心理阴影，所以没有选择积分，而是选择了一个近似算法。李晔晨认为I已经可以做了，就直接去想G。我由于把I这种数学题完全交给了李晔晨，结果没有去验证他的想法，这导致了我们在最后2个小时非常被动。

接下来，我们在经过一番讨论之后终于发现了B是一个弱智题目，被我秒杀。于是全场还有CDGIJ没做。我们对于GIJ都有想法，于是决定先写这三个题目。由于J比较稳，而我由于没有肖刘那么擅长写这种递推的程序，所以就交给了肖刘写，果然不负众望的AC了。然后写I，TLE之，当时我还没有感觉出来有什么问题，其实这个算法注定是错误的，关键在于精度不够。然后又写了G，由于这两个题目都是李晔晨负责的，所以在最后的一个半小时之内比赛变得非常混乱。虽然最后李晔晨不负众望过了I，肖刘也极尽所能的AC了G，但是我们这一阶段的安排确实很有问题。

9 北京大学 弓箭手 8 1664 金奖

我们队最后是8个题，但是由于G和I交了很多次，罚时较多，只有第9名。赛后得知C是模板题，被赖陆航他们恶搞过了，D是一个DLX，但是很难写。 我们这次比赛最大的失误在于题目分配不均衡，主要过错在于我没有能够完全发挥自身的能力。AEJ是肖刘写的，FGHI是李晔晨写的，我仅仅只写了一个很简单的B。在今后的比赛中，我们应该加强中间一段时间题目分配的均衡程度，确保不会有一个人做多个题的情况。前期还是可以让肖刘主写简单题，我看题，而且一开始就可以分配一些难题给李晔晨，这样可以防止后期乏力的问题。如果可以继续加强磨合，相信我们这支目前还算是比较稚嫩的队伍可以在今后的比赛中取得更好的成绩。

NEERC2005主页在这里。

题目给定n和k，要求。

我们先找一下规律，发现与等差数列是有关系的。我们对于当前的i，令，。那么当i增大1时，如果q不变，p一定减少了q，那么将p一直减小到0，同时对这一段进行求和（用数列求和公式），同时i增大到下一段的开头。

详细情况见代码：

#include <cstdio>
#include <algorithm>

using namespace std;

int n,k;

__int64 sum(int a,int d,int n) {
  return (__int64)(2*a-d*n)*(n+1)/2;
}

int main() {
  freopen("joseph.in","r",stdin);
  freopen("joseph.out","w",stdout);
  scanf("%d%d",&n,&k);
  int i = 1,p,q,a;
  __int64 r = 0;
  while (i<=n) {
    q = k%i; p = k/i;
    if (p>0) a = q/p;
    else a = INT_MAX;
    r += sum(q,p,min(a,n-i));
    i += min(a,n-i)+1;
  }
  printf("%I64d\n",r);
  return 0;
}