我太弱了，打一下我的70分做法quq：
$ \sum_{i=1}^{n} \sum_{j=1}^{m} \phi(gcd(i, j)) $
$ = \sum_{d=1}^{n} \sum_{i=1}^{n} \sum_{j=1}^{m} \phi(gcd(i, j)) [gcd(i, j) == d]$
$ = \sum_{d=1}^{n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} \phi(d*gcd(\frac{i}{d}, \frac{j}{d})) [gcd(\frac{i}{d}, \frac{j}{d}) == 1]$
$ = \sum_{d=1}^{n} \phi(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [gcd(\frac{i}{d}, \frac{j}{d}) == 1]$
设$ F(n, m) = \sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i, j) == 1]$
则原式
$ = \sum_{d=1}^{n} \phi(d) F(\lfloor \frac{n}{d} \rfloor, \lfloor \frac{m}{d} \rfloor)$
F的计算参见 HAOI2011 问题B
分块优化，单次查询时间复杂度应该是接近O(n)的？
Orz

700题留念，感谢神犇Itachi的悉心教导！

没输出回车，A掉了……

Ezoi 占领预警！~

回复 @OI再见 :
学长，1.5s也可以过啊。。。

改改时限吧，2s

膜拜神犇@OI再见