| 题目名称 | 2431. [HZOI 2016]艾米利亚的求助 |
|---|---|
| 输入输出 | aimiliyadehelp.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Sky_miner
于2016-08-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：35， 提交：85， 通过率：41.18% | ||||
 卜卜 |
100 | 0.016 s | 0.31 MiB | C++ |
 MistyEye |
100 | 0.163 s | 0.32 MiB | C++ |
 kito |
100 | 0.472 s | 0.29 MiB | C++ |
 FoolMike |
100 | 0.585 s | 0.31 MiB | C++ |
 梦那边的美好ET |
100 | 0.809 s | 3.16 MiB | C++ |
 _Itachi |
100 | 0.844 s | 1.05 MiB | C++ |
 半汪 |
100 | 0.861 s | 0.31 MiB | C++ |
 zcysky |
100 | 0.869 s | 0.31 MiB | C++ |
|
Go灬Fire |
100 | 0.916 s | 0.31 MiB | C++ |
 sxysxy |
100 | 0.932 s | 0.29 MiB | C++ |
| 关于 艾米利亚的求助 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
一开始没看见F(1) = 0。按一般的约数个数函数推了，后来发现了，一慌：读错题了，但是忽然想到F(1) = 0不过是把gcd == 1的贡献减去了而已。。。写一下推的过程：
设 $ D(x) = \sum_{d|x}^{ } 1 $ 也就是x的约数的个数。（与本题中F的区别就是$ D(1)=1 $) $ \sum_{i=1}^{n} D(gcd(i, n)) = \sum_{d|n}^{ } \sum_{k=1}^{\lfloor \frac{n}{d} \rfloor} D(d) [gcd(k, \frac{n}{d}) == 1] $ $ = \sum_{d|n}^{ } D(d) * \sum_{k=1}^{\lfloor \frac{n}{d} \rfloor} [gcd(k, \frac{n}{d}) == 1] $ $ = \sum_{d|n} D(d) * \phi(\frac{n}{d})$ 发现是个狄利克雷卷积的形式，我们先变换一下：(下面这个$ * $表示狄利克雷卷积运算) $ = D * \phi$ = $ 1 * 1 * \phi$ = $ id * 1$ 到这里求解就非常容易了，就是 $ = \sum_{d|n} \frac{n}{d} $ 那原题里面不是D函数，而是F，区别在于$ F(1) = 0 $，怎么办 注意到原式子 $\sum_{i=1}^{n} F(gcd(i, n))$ ，我们求出来的是 $ \sum_{i=1}^{n} D(gcd(i, n))$，只有$ gcd(i, n) == 1 $ 的时候，F和D有偏差。 对于每一个$ gcd(i, n) == 1 $ ，我们都刚好多算了$ 1 $，所以最后我们答案多算了$ \phi(n) $，减去即可。 最终 $ Ans = \sum_{d|n} \frac{n}{d} - \phi(n) $ 可以在$ O(\sqrt{n})$ 的时间复杂度内求解出来。 | ||||
|
回复 @kito :
好吧...... 看到N好大就不敢写根号 卜卜
2017-04-07 15:36
13楼
| ||||
|
回复 @卜卜 :
30000000还是可以承受的吧。而且出题人没造极限数据，达不到$O(\sqrt n)$ kito
2017-04-02 07:32
12楼
| ||||
|
根号算法为啥能过啊？？ 这么多零一看就感觉会TLE 感觉只能用Pollard_Rho诶
卜卜
2017-04-01 22:27
11楼
| ||||
|
太轻视了，被运算顺序搞跪了
先是ans*=(x-1)/x，先算(x-1)/x，后相乘 改成ans=ans*(x-1)/x，结果先算ans*(x-1)，一个大数爆unsigned long long了 怒跪  New World
2017-01-04 10:11
10楼
| ||||
|
回复 @Pessimist :
这个题好像不需要数组吧 | ||||
|
数组开太大会超时，不大不小，1000适合你
 Magic_Sheep
2016-09-21 11:03
8楼
| ||||
|
VIPEzoi 占领此题 Orz...LPX
 沉迷学习的假的Keller
2016-09-21 10:46
7楼
| ||||
|
为什么一个素数点都没有
| ||||
|
EZOI即将占领此题
LPX Orz  Hakurou!
2016-09-21 10:22
5楼
| ||||
Ezoi_Vermouth2431. [HZOI 2016]艾米利亚的求助
★★★ 输入文件：aimiliyadehelp.in
输出文件：aimiliyadehelp.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
在菜月昴成功帮助贝蒂计算出来了提升魔法强度式子的值后，艾米利亚和贝蒂对菜月昴的好感度瞬间上升，贝蒂也成功应用这个数据成功加强了艾米利亚的魔法强度。
可是现在问题来了，因为魔法咒语的强度大大加强，艾米利亚想要记住这些咒语并且刻录在记忆中的难度大大加强，于是艾米利亚又找到了贝蒂，想要贝蒂帮助一下艾米利亚。然而贝蒂发现，艾米利亚无法记住咒语的真正原因并不是魔法强度太大，而是因为艾米利亚被下了术式！而前几天和艾米利亚接触的除了菜月昴就只有“善良的村民们”，但是由于菜月昴刚刚帮助了自己，所以艾米利亚并没有怀疑菜月昴。
这个术式非常高深，不过我们的贝蒂不是吃闲饭的，迅速推演出了破解术式需要的咒语。但是正在贝蒂准备施展咒语的时候。术式突然发动了，但是这个术式非常不稳定，是可以暂时镇压下来的。
可是我们的贝蒂正在施法，没有办法停下来镇压术式。这时，艾米利亚看到了前面的菜月昴，掏出了一卷咒语，告诉菜月昴只要施展这个咒语就可以镇压艾米利亚的术式，而这个咒语恰好是阴属性的，所以菜月昴完全可以掌握这个咒语。
然而菜月昴在刻印咒语的时候，遇到了一个难题，这个咒语要求施法者必须灵活处理暗元素的流动，然而菜月昴发现，如果要合理的处理暗元素的流动就必须计算出这个式子:
其中F(x)表示x的因子个数
而且每一次要处理暗元素的流动需要计算的N值还不一样。
所以不会编程的菜月昴一脸萌币，再一次通过四维空间泡上的无形波动，穿过了无数低光速黑洞通过wifi联系到了你。
希望你能帮助他解决这个问题。
当然啦，作为报酬，菜月昴拍下了艾米利亚的一张图片送给你。。。
【输入格式】
一行，一个正整数N
【输出格式】
一行，为式子的结果
【样例输入1】
1
【样例输出1】
0
【样例输入2】
2
【样例输出2】
2
【提示】
$1 <= N <=1000000000000000$
我们认为$F(1) = 0$
【来源】
HZOI 2016