[Codeforces Round #538(Div.2)] 1114F-Please, another Queries on Array?

坚持每天一道难度 2500 以上的题!

题目链接(1114F)

题目就是维护区间积的欧拉欧拉欧拉欧拉欧拉欧拉函数辣~

注意到每个数最多也就 $300$,然后根据 $\varphi(n)=n\times \prod\limits_{i=1,p_i|n}(1-\frac{1}{p_i})$ 我们可以先筛出 $300$ 以内的素数,发现只有 $62$ 个,就可以用一个 long long 的状态来存这个区间有哪些素因子,然后就是普通的线段树维护辣~

 

发表评论