题解
题解
题目让求(sum_{i=1}^{n}sum_{j=1}^{n}f(gcd(i,j))^k)
(f)代表次大质因子
先反演化简一波式子
(sum_{t=1}^{n}f(t)^ksum_{i=1}^{n}sum_{j=1}^{n}[gcd(i,j)]= t]\
sum_{t=1}^{n}f(t)^ksum_{d=1}^{frac{n}{t}}mu(d)lfloorfrac{n}{dt}
floor^2\
sum_{T=1}^{n}lfloorfrac{n}{T}
floor^2sum_{d|T}mu(d)f(frac{T}{d})^k)
然后就可以去筛函数(F(T)=sum_{d|T}mu(d)f(frac{T}{d})^k)了
那么来考虑这玩意儿在非线性时间内怎么筛出来?
可以发现这个函数是用狄利克雷卷积来定义的,而且这个函数还包括了(mu),所以可以考虑杜教筛
考虑用(I)与(F)做狄利克雷卷积
(I * mu * f=(I * mu)*f=e*f=f)
所以我们在杜教筛中要快速求的狄利克雷卷积后的前缀和就是求(f)的前缀和了
(f)代表了次大质因子
所以可以考虑用(min25)筛来处理
具体做法就是先处理出(g(i))表示(le i)的质数的个数
然后考虑每个质数(p_i)的贡献
只有当分解到只剩下两个质数的时候再计算贡献
(p_i)的贡献就是当前所有比(p_i)大的质数的个数( imes p_i^k)
然后在枚举最小质因数的若干次方的时候顺便计算最大质因数和次大值因数相同的情况
具体就是这样筛的
int S(int x , int j) {
if(x <= 1 || pri[j] > x) return 0 ;
int ret = prik[j - 1] * (g[Gid(x)] - j + 1) ;
// 只剩下p[j-1]和另外一个比ta大的质数
for(int i = j ; i <= pnum && pri[i] * pri[i] <= x ; i ++) {
LL p1 = pri[i] , p2 = pri[i] * pri[i] ;
for( ; p2 <= x ; p1 = p2 , p2 *= pri[i] )
ret += S(x / p1 , i + 1) + prik[i] /*最大质因数和次大质因数相同的数 */;
}
return ret ;
}
总复杂度(O(n^{frac{3}{4}}))
有点卡常数
代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
# define LL long long
# define uit unsigned int
const int M = 200005 ;
using namespace std ;
bool notp[M] , vis1[M] , vis2[M] ;
int n , m , sz , idk , pnum ;
int w[M] , id1[M] , id2[M] , pri[M] ;
uit ans , prik[M] , g[M] , f1[M] , f2[M] ;
inline int Gid(int x) {
return (x <= sz) ? id1[x] : id2[n / x] ;
}
inline uit Fpw(uit Base , int k) {
uit temp = 1 ;
while(k) {
if(k & 1) temp = temp * Base ;
Base = Base * Base ; k >>= 1 ;
}
return temp ;
}
inline void presolve(int n) {
for(int i = 2 ; i <= n ; i ++) {
if(!notp[i]) pri[++pnum] = i , prik[pnum] = Fpw((uit)i , idk) ;
for(int j = 1 ; j <= pnum && i * pri[j] <= n ; j ++) {
notp[i * pri[j]] = true ;
if(i % pri[j] == 0) break ;
}
}
}
uit S(int x , int j) {
if(x <= 1 || pri[j] > x) return 0 ;
uit ret = prik[j - 1] * (g[Gid(x)] - j + 1) ;
for(int i = j ; i <= pnum && pri[i] * pri[i] <= x ; i ++) {
LL p1 = pri[i] , p2 = pri[i] * pri[i] ;
for( ; p2 <= x ; p1 = p2 , p2 *= pri[i] )
ret += S(x / p1 , i + 1) + prik[i] ;
}
return ret ;
}
inline uit Calc(int n) {
if(vis2[Gid(n)]) return f2[Gid(n)] ;
f2[Gid(n)] = S(n , 1) ; vis2[Gid(n)] = true ;
return f2[Gid(n)] ;
}
uit Solve(int n) {
if(n <= 1) return 0 ;
if(vis1[Gid(n)]) return f1[Gid(n)] ;
uit ret = Calc(n) + g[Gid(n)] ;
for(int l = 2 , r ; l <= n ; l = r + 1) {
r = n / (n / l) ;
ret -= (r - l + 1) * Solve(n / l) ;
}
vis1[Gid(n)] = true ; f1[Gid(n)] = ret ;
return ret ;
}
int main() {
scanf("%d%d",&n,&idk) ;
sz = sqrt(n) ; presolve(sz) ;
for(int l = 1 , r ; l <= n ; l = r + 1) {
r = n / (n / l) ; w[++m] = n / l ;
if(w[m] <= sz) id1[w[m]] = m ;
else id2[n / w[m]] = m ;
g[m] = w[m] - 1 ;
}
for(int j = 1 ; j <= pnum ; j ++)
for(int i = 1 ; i <= m && pri[j] * pri[j] <= w[i] ; i ++)
g[i] -= g[Gid(w[i] / pri[j])] - j + 1 ;
for(int l = 1 , r ; l <= n ; l = r + 1) {
r = n / (n / l) ;
ans += (uit)(n / l) * (n / l) * (Solve(r) - Solve(l - 1)) ;
}
printf("%u
",ans) ;
return 0 ;
}