Vijos已经很久没有办过比赛了。
但Vijos不希望被大家遗忘，并依然憧憬着给更多的小盆友带来一段难忘的回忆。

适逢金秋十月，桂花香飘。正是重聚的好时机。
于是我们决定，重新开始举办NOIP模拟赛。陪伴即将踏上NOIP赛场的小盆友们，蓄势扬帆。

题目难度：NOIP提高组
比赛链接：https://vijos.org/contest/59d0c6cbd3d8a127fd789176

评测机配置：

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 62
model name  : Intel(R) Xeon(R) CPU E5-2630 v2 @ 2.60GHz
stepping    : 4
microcode   : 0x428
cpu MHz     : 1199.865
cache size  : 15360 KB
physical id : 0
siblings    : 12
core id     : 0
cpu cores   : 6
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
flags       : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm epb tpr_shadow vnmi flexpriority ept vpid fsgsbase smep erms xsaveopt dtherm ida arat pln pts
bugs        :
bogomips    : 5199.65
clflush size    : 64
cache_alignment : 64
address sizes   : 46 bits physical, 48 bits virtual
power management:

除非题目说明，默认内存限制256MiB。
目前Java好像是坏的。。。

2017.10.2: 比赛准备中...
2017.10.5: 题目出好啦，感觉考点挺全面的呢...
2017.10.7:
17:53 还有一会比赛就要开始了，祝大家玩得开心
18:03 可以重复提交，最后一次为准
18:06 大家可以在这里提问
18:43 补充了第一题中d的范围
21:12 比赛还有不到一个小时就要结束了，大家加油
21:58 比赛即将结束，成绩将在赛后约5分钟内给出
21:59 感谢大家的参与，送给大家Pete Seeger的名曲Little Boxes，希望大家有一个愉快的夜晚
http://www.xiami.com/song/creDUeff19?spm=a1z1s.6659509.0.0.zbvUEu

22:05 题目将在15分钟内开放到题库中
22:14 题目已经加入到题库中，题解正在筹备中，也欢迎大家在题解区留下自己的想法

第一题、
需要分析出来每一条边的最大可能长度如果不是这两点间最短路径的长度 \(d\) ，那么就一定可以任意大。那么什么时候 \(i\) 到 \(j\) 的变长度可以不是 \(d\) 呢？一定是存在第三个点 \(k\) 满足 \(d(i,k)+d(k,j)=d(i,j)\)。这就得到了一个 \(O(n^3)\) 的算法。
作为拓展思考：这一题其实可以做到 \(O(n^2 \lg{n})\)。

第二题、
注意到 \(\phi(n)/(n-1)\) 展开后等于 \(n/(n-1)\) 乘上若干个 \(p/(p-1)\) 这里 \(p\) 是 \(n\) 的素因子，且 \(p\) 不会重复出现。那么换句话说除了前面 \(n/(n-1)\) 后面部分的结果与一个素因子在 \(n\) 中出现多少次没有关系。进而想到如果不考虑 \(n/(n-1)\) 只看后面部分的乘积，最优方案一定是最小若干个素数的乘积。也就是 \(2, 2\times 3, 2\times 3\times 5, 2\times 3\times 5\times 7, 2\times 3\times 5\times 7\times 11\)等。而多了 \(n/(n-1)\)，答案应该是上述形式的倍数，且不会倍率非常大（因为 \(n\) 比较大的时候 \(n/(n-1)\) 几乎等于 \(1\)）。这就得到了最终的算法。

第三题、
这一题是一道比较经典的数位类动态规划。
只需要注意到所谓的修改实际上不外乎在把最大的数字改成 \(0\) 和把最小的数字改成 \(9\) 之间，还需要稍微额外考虑一下最高位的特殊情况。

第四题、
一道比较常规的数据结构题。作为NOIP模拟题，我给出的建议算法是分块，尤其注意到所有符号都是 \(0\) 或 \(1\) ，所以实际上还可以压位。
当然也存在一般的做法，就是利用Splay维护字符串Hash，并支持相关的修改和询问。