Description：

设函数 $f_r(n)$ ： $$ f_0(n)=\sum_{u\times v=n}[\gcd(u,v)=1] $$

$$ f_r(n)=\sum_{u\times v=n}\frac{f_{r-1}(u)+f_{r-1}(v)}2 $$

求 $f_r(n)$ 。

$1\leqslant testcases,r,n\leqslant10^6$

Solution：

首先考虑 $f_0(n)$ ，既然要求两部分互质，也就是说不能有共同质因数，那么 $n$ 的每个质因子要么全在 $u$ 要么全在 $v$ ，方案数是 $2^\text{质因子个数}$ ，所以 $f_0(n)$ 是不完全积性的，归纳一下： $$ f_r(n)=\sum_{u\times v=n}\frac{f_{r-1}(u)+f_{r-1}(v)}2=\sum_{d|n}f_{r-1}(d) $$

所以有结论： $f_r=1\times f_{r-1}$ ，由狄利克雷卷积的性质可得，若 $f_{r-1}$ 积性 $，f_r$ 也积性。所以 $f_r$ 是积性的。

考虑如何快速求积性函数，积性函数有一个重要的性质就是 $\begin{align}f(n)=\prod_{i=1}^mf(p_i^{t_i})\end{align}$ ，也就是说决定积性函数值的是这个函数在质数的幂处的取值，如果是完全积性函数就是在质数处的值，只要这些确定了，整个函数在 $\N^*$ 的值就唯一确定了，再次观察这个函数，发现所有的 $f(p_i^w)$ 都相同，证明也是利用归纳， $f_0(p_i^w)$ 肯定满足， $\begin{align}f_r(p_i^w)=\sum_{k=0}^wf_{r-1}(p_i^k)\end{align}$ ，跟 $p_i$ 没有什么关系，所以也无关，然后就可以先筛出来所有质数，然后用刚才那个式子求出所有的 $f_r(p^k)$ ，用 $f_r$ 前缀和的性质时间复杂度是 $O(n^2)$ 的，最后分解 $n$ 乘一下就行了，分解可以在线性筛的时候预处理一个最小质因子的幂和幂次，由于每次至少减半，所以复杂度是 $O(\log n)$ 的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,q;

#define MAXN 200010

struct option

{

	int x,d,l;

}q[MAXN];

struct node

{

	int lc,rc;

	int tag,maxv;

}tr[2][MAXN << 1];

int ptr[2] = {0};

int newnode(int k){return ++ptr[k];}

int root[2];

#define mid ((l + r) >> 1)

#define t tr[c]

void build(int c,int rt,int l,int r)

{

	rt = newnode(c);

	if(l == r)return;

	build(c,t[rt].lc,l,mid);

	build(c,t[rt].rc,mid + 1,r);

	return;

}

int main()

{

	scanf("%d%d",&n,&q);

	int x,d,l;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d%d",&q[i].x,&q[i].d,&q[i],l);

	}

	build(0,root[0],1,n);

	build(1,root[1],1,n);

	

	

	

	return 0;

}