题目名称	2432. [HZOI 2016]艾米利亚的施法
输入输出	`aimiliyausemagic.in/out`
难度等级	★★★
时间限制	1500 ms (1.5 s)
内存限制	256 MiB
测试数据	10
题目来源	Sky_miner 于2016-08-13加入
开放分组	全部用户
提交状态
分类标签
	分享题解

通过：31，提交：71，通过率：43.66%
kito	100	2.263 s	173.87 MiB	C++
河北交通广播992大师来了	100	2.309 s	200.57 MiB	C++
The dark	100	2.332 s	124.27 MiB	C++
New World	100	2.335 s	200.62 MiB	C++
kito	100	2.345 s	156.48 MiB	C++
Go灬Fire	100	2.897 s	200.59 MiB	C++
可以的.	100	3.530 s	200.57 MiB	C++
shy	100	3.995 s	191.27 MiB	Pascal
zcysky	100	4.046 s	152.90 MiB	C++
可以的.	100	4.619 s	200.57 MiB	C++

关于艾米利亚的施法的近10条评论(全部评论)
我太弱了，打一下我的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 sxysxy 2017-05-18 01:20 7楼
700题留念，感谢神犇Itachi的悉心教导！ FoolMike 2017-02-18 20:53 6楼
没输出回车，A掉了…… 半汪 2017-01-08 10:12 5楼
Ezoi 占领预警！~ Ezoi_强势占领 2016-09-22 14:08 4楼
回复 @OI再见 : 学长，1.5s也可以过啊。。。 Sky_miner 2016-08-15 06:05 3楼
改改时限吧，2s Foenix 2016-08-14 18:56 2楼
膜拜神犇@OI再见 AntiLeaf 2016-08-14 18:51 1楼

2432. [HZOI 2016]艾米利亚的施法

★★★ 输入文件：aimiliyausemagic.in 输出文件：aimiliyausemagic.out 简单对比
时间限制：1.5 s 内存限制：256 MiB

【题目描述】

艾米利亚在菜月昴和贝蒂的帮助下，成功解除了术式。现在艾米利亚终于可以来施展一下经过加强的法术咒语了。

但是贝蒂在时候突然有事，要参加对第八维空间开拓的作战，于是贝蒂通过四维空间泡的无形波动，穿越了无数的低光速黑洞，来到了四维空间。又通过五维空间泡上的无形波动，穿越了无数的极低光速黑洞，来到了五维空间。又通过六维空间泡上的无形波动，穿越了无数的更低光速黑洞，来到了六维空间。又通过七维空间泡上的无形波动，穿越了无数的零光速黑洞，来到了七维空间。然后通过大精灵创建的传送门来到了八维魔界处。。。。。。

然而这跟我们并没有什么关系呢。

艾米利亚准备在庭院中施展她的咒语，菜月昴和帕克在一旁助威。之间艾米利亚的身周缓缓冒出了许多的光球。

“哇！那些光球是什么！！！是艾米利亚的魔法元素吗？”菜月昴惊喜的喊道。

“不，那些是小精灵。艾米利亚的这个咒语必须在沟通小精灵的情况下才可以施展出最大的威力”帕克伸了个懒腰，缓缓地说道。

“帕克、菜月昴!快帮帮我这些小精灵突然变得非常急躁，我无法和他们交流”艾米利亚突然焦急地说道。

“恩。。。不会吧，，这是初学魔法的人才会出现的。。。诶？不对！你的咒语为什么包含着阴属性？这不是你的属性啊！”帕克突然变了脸色，失声叫道。

“这。。。好像是我的属性，让我试试看能不能解决它”菜月昴站出来说道。

“你才初涉魔法，还是先不要。。。”

“那太好了，菜月昴，我现在就把小精灵传递过来的信息转移出一部分”艾米利亚直接打断了帕克的话，说道。

“。。。。。。”帕克退到了一旁，默默地看着。。

我们的男主菜月昴可能会和小精灵交流吗？当然不会啦。。。。。。

只是他知道可以通过四维空间泡上的无形波动，然后穿过无数的低光速黑洞来联系到你。

但是你并不打算帮他呢。。。

可是，菜月昴发过来了一张图片，让你欲罢不能（艾米利亚和小精灵交流的画面太美啦），你还是打算帮一帮菜月昴。

艾米利亚传过来的信息包括两个正整数N,M,你需要做的是，就是计算出

以此来帮助艾米利亚和小精灵的沟通

菜月昴传来了多个N,M,因为和不同的小精灵沟通需要的值也不同，所以菜月昴必须处理多次N,M;

【输入格式】

第一行一个正整数T,表示需要处理的N,M的数量

接下来T行，每行两个正整数N,M

【输出格式】

共T行，每一行包括输入的N,M所对应的答案

【样例输入1】

1
5 5

【样例输出1】

【样例输入2】

1
100 152

【样例输出2】

【提示】

对于20%的数据，N,M<=2000

对于50%的数据，N,M<=300000

对于70%的数据，N,M<=1000000

对于100%的数据，N,M<=10000000

对于70%的数据，T<=3,对于100%的数据，T<=1000

【来源】

HZOI 2016