description

给你一个空的可重集合\(S\)。

\(n\)次操作，每次操作给出\(x\),\(k\),\(p\)，执行以下操作：

\(opt\ 1\):在S中加入x。

\(opt\ 2\):输出

\[\sum_{y\in S}gcd(x,y)^k\]

data range

所有输入的数都是小于\(10^5+1\)的正整数。

solution

考场降智系列

对于一个\(x\)，其\(gcd(x,y)\)有\(O(d(x))\le O(\sqrt x)\)个

这里\(d(x)\)指\(x\)的约数个数

枚举\(x\)的约数\(d\),考虑如何算出\(gcd(x,y)==d\)的\(y\)的个数

我们可以\(O(n\sqrt x)\)地动态维护集合\(S\)内\(i\)的倍数的数的个数\(p[i]\)。

但是\(d\)的倍数和\(x\)的\(gcd\)显然不一定是\(d\)。

这里有一个可能比较简单的容斥做法:

考虑一开始\(gcd(x,y)==x\)的数的个数肯定是\(=p[x]\)的。

于是可以在\(p[i<x]\)中减掉\(p[x]\).

之后\(x\)的次大的约数也会变成正确答案;

这样逐级做下去即可求出我们需要的答案。

复杂度?

看起来是\(O(n\sqrt n\sqrt{\sqrt n})=O(n^{\frac{7}{4}})\)的...

但是\(=O(能过)\)。

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include