class="markdown_views prism-atom-one-light"> Description 给出n,K" role="presentation" style="position: relative;">n,K$n,K$，令si=∑j≤ijK" role="presentation" style="position: relative;">si=∑j≤ijK$s_i=\sum _{j\le i}{j}^K$，求∑1≤i≤nsi[gcd(i,n)=1]" role="presentation" style="position: relative;">∑1≤i≤nsi[gcd(i,n)=1]$\sum _{1\le i\le n}{s}_i[gcd(i,n)=1]$ Input 第一行一整数T" role="presentation" style="position: relative;">T$T$表示用例组数，每组用例首先输入一整数K" role="presentation" style="position: relative;">K$K$，之后输入一整数m" role="presentation" style="position: relative;">m$m$表示n" role="presentation" style="position: relative;">n$n$的素因子数量，最后输入m" role="presentation" style="position: relative;">m$m$对整数pi,ai" role="presentation" style="position: relative;">pi,ai$p_i,a_i$表示n=∏i=1npiai" role="presentation" style="position: relative;">n=∏i=1npaii$n=\prod _{i=1}^n{p}_i^{a_i}$ (K≤105,∑K≤106,m≤20,pi,ai≤109,pi<pi+1)" role="presentation" style="position: relative;">(K≤105,∑K≤106,m≤20,pi,ai≤109,pi<pi+1)$(K\le {10}^5,\sum K\le {10}^6,m\le 20,p_i,a_i\le {10}^9,p_i<p_{i+1})$ Sample Input 2
1
2
2 1
3 1
233
1
23333 1 Sample Output 16
32727388 Solution 对所求表达式反演有
ans=∑i=1n[(i,n)=1]∑j=1ijK=∑i=1n∑d|(i,n)μ(d)S(i,K)=∑d|nμ(d)∑i=1ndS(id,K)" role="presentation">ans===∑i=1n[(i,n)=1]∑j=1ijK∑i=1n∑d|(i,n)μ(d)S(i,K)∑d|nμ(d)∑i=1ndS(id,K)$$\begin{array}{rcl}ans& =& \sum _{i=1}^n[(i,n)=1]\sum _{j=1}^i{j}^K\\ & =& \sum _{i=1}^n\sum _{d|(i,n)}\mu (d)S(i,K)\\ & =& \sum _{d|n}\mu (d)\sum _{i=1}^{\frac{n}{d}}S(id,K)\end{array}$$
其中S(n,k)=∑i=1nik=1k+1∑i=1k+1Ck+1iBk+1−i(n+1)i" role="presentation" style="position: relative;">S(n,k)=∑i=1nik=1k+1∑i=1k+1Ci