Uoj#38. 【清华集训2014】奇数国
题意:
- 有$n$个数,开始每个数均为$3$。
- 有两种操作:
- 修改某个数。
- 查询区间乘积的欧拉函数值。
- 保证每个数只包含前$60$个质因子。
- $1\le n\le 10^5$。
题解:
- 一个数$x$的欧拉函数值可以表示为$x\times \prod_{P_i|x}\frac{P_i-1}{P_i}$。
- 所以维护区间乘积以及一段区间出现的质数集合即可。
- 开两棵线段树维护,复杂度$O(60n+n\log n)$。
代码:
1 |
|
1 | #include <iostream> |
本文标题:Uoj#38.【清华集训2014】奇数国
文章作者:wzf2000
发布时间:2018年04月18日 - 15:04
最后更新:2018年04月27日 - 11:04
原始链接:https://wzf2000.github.io/2018/04/18/Uoj38/
许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。