2013-team1-0917

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

比赛链接： http://acm.hust.edu.cn/vjudge/contest/view.action?cid=31766#rank

== 小结 ==

=== by yxdb ===
今天我做的两题（C和H）基本和全场最快过的人差不多速度，可以说我这个点上发挥还不错。B题我最后想出了做法，赛后看了题解发现和标程的做法一样。比较不足的是A题没搞出来，另外似乎有比A题更简单的题我们没开……本场我们比较惨的一个地方是J题没过，而且浪费了他们俩很长时间，要不然我应该可以写完B题的……

赛后看解题报告，感觉我们数学还是比较薄弱的，我赶紧取补充一下数论和组合计数的知识，在regional之前搞定。然后这场还有一个问题是E题我和mm都不知道题意，这几场训练下来，感觉如果我们队中期卡题的话，可能会导致中后期交流不够，这点以后要注意一下

B题赛后已补，在打包代码中了。

终于懂A题的题解是什么意思了！！！现在把模型化简一下：

  给出n个整数：a1, a2, ..., an。求式(1)： sum(gcd(ai, aj)) (1 <= i < j <= n)。
  解法： 式(2)： sum(Comb(num(d), 2) * phi(d))。
  其中 num(d) 表示这n个数中是d的倍数的数量。'''而 phi(d) 是欧拉函数。'''
  下面证明 式(2) = 式(1)：
  考虑对于某一对数 ai, aj (1 <= i < j <= n)。记 g = gcd(ai, aj)，则式(1)中，会加上这个g。
  设 g 的约数分别为 d1, d2, ..., dk，则有式(3)： phi(d1)+phi(d2)+...+phi(dk) = g。
  而在式(2)中，对于每一个di，最后的和中恰好会加上phi(di)，根据式(3)， 式(2)对于这一对数ai, aj总共加上了g。
  而对于每一对数 ai, aj，以上分析均成立。所以式(2) = 式(1)。

所以对于每个询问，需要求出[Li, Ri]区间内的num[d]。这个是可以分块维护的，具体看代码。

比赛链接： http://acm.hust.edu.cn/vjudge/contest/view.action?cid=31766#rank

小结

by yxdb

今天我做的两题（C和H）基本和全场最快过的人差不多速度，可以说我这个点上发挥还不错。B题我最后想出了做法，赛后看了题解发现和标程的做法一样。比较不足的是A题没搞出来，另外似乎有比A题更简单的题我们没开……本场我们比较惨的一个地方是J题没过，而且浪费了他们俩很长时间，要不然我应该可以写完B题的……

赛后看解题报告，感觉我们数学还是比较薄弱的，我赶紧取补充一下数论和组合计数的知识，在regional之前搞定。然后这场还有一个问题是E题我和mm都不知道题意，这几场训练下来，感觉如果我们队中期卡题的话，可能会导致中后期交流不够，这点以后要注意一下

B题赛后已补，在打包代码中了。

终于懂A题的题解是什么意思了！！！现在把模型化简一下：

给出n个整数：a1, a2, ..., an。求式(1)： sum(gcd(ai, aj)) (1 <= i < j <= n)。

解法： 式(2)： sum(Comb(num(d), 2) * phi(d))。

其中 num(d) 表示这n个数中是d的倍数的数量。而 phi(d) 是欧拉函数。

下面证明 式(2) = 式(1)：

考虑对于某一对数 ai, aj (1 <= i < j <= n)。记 g = gcd(ai, aj)，则式(1)中，会加上这个g。

设 g 的约数分别为 d1, d2, ..., dk，则有式(3)： phi(d1)+phi(d2)+...+phi(dk) = g。

而在式(2)中，对于每一个di，最后的和中恰好会加上phi(di)，根据式(3)， 式(2)对于这一对数ai, aj总共加上了g。

而对于每一对数 ai, aj，以上分析均成立。所以式(2) = 式(1)。

所以对于每个询问，需要求出[Li, Ri]区间内的num[d]。这个是可以分块维护的，具体看代码。

附加文件