「P6156 简单题」加强版

题目描述

思路

\sum\limits_{i = 1}^n\sum\limits_{j = 1}^m(i+j) ^k \gcd(i,j) \mu^2(\gcd(i , j))

套路枚举 $d$

= \sum_{d = 1} ^n\mu^2(d)d\sum_{i=1}^n\sum\limits_{j = 1}^m [\gcd(i,j) = d](i+j)^k

换元

= \sum_{d = 1} ^n\mu^2(d)d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j = 1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(i,j) = 1](id+jd)^k

利用 $[n=1]=\sum_{d \mid n} \mu(d)$ 化简

= \sum_{d = 1} ^n\mu^2(d)d^{k+1}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j = 1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(i,j) = 1](i+j)^k

= \sum_{d = 1} ^n\mu^2(d)d^{k+1}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j = 1}^{\lfloor \frac{m}{d} \rfloor} \sum_{x \mid i,x \mid j}\mu(x)(i+j)^k

= \sum_{d = 1} ^n\mu^2(d)d^{k+1}\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{x \mid i}^{\lfloor \frac{n}{dx} \rfloor}\sum\limits_{x \mid j}^{\lfloor \frac{m}{dx} \rfloor}(i+j)^k

设 $F(x) = \sum_{i=1}^{x} \sum_{j = 1}^x (i+j)^k$

\sum_{d=1}^n \mu^2(d)d^{k+1} \sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} F(\lfloor \frac{n}{dx} \rfloor)

令 $T = dx$

\sum_{T=1}^n T^k F(\lfloor \frac{n}{d} \rfloor)\sum_{d \mid T}\mu^2(d)\mu(\frac{T}{d})

观察这个柿子，那么有两个函数可以线性筛 $i^k$ 与 $\sum_{d \mid T}\mu^2(d)\mu(\frac{T}{d})$ ，那么线性筛即可（没学过线性筛的可以看
P4449 于神之怒加强版 )

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e7 + 10;
const long long Mod = 2147483658;

long long N , K , T , n;

int Prime[MAXN / 10] , Cnt;
unsigned int F[MAXN] , S[MAXN];
bitset<MAXN> Vis;

unsigned int Quick_Power(int x , int mi) {
    unsigned int Ans = 1;
    for(; mi ; mi >>= 1, x = 1ll * x * x)
        if(mi & 1) Ans = 1ll * Ans * x;
    return Ans;
}

void Get_Function(int N) {
    F[1] = S[1] = 1;
    for(int i = 2; i <= N; i++) {
        if(!Vis[i]) {
            Prime[++Cnt] = i;
            S[i] = Quick_Power(i , K);
            F[i] = i - 1;
        }
        for(int j = 1; j <= Cnt && Prime[j] * i <= N; j++) {
            Vis[i * Prime[j]] = 1;
            S[i * Prime[j]] = 1ll * S[i] * S[Prime[j]];
            if(i % Prime[j] == 0) {
                 if(i / Prime[j] % Prime[j] != 0)
                    F[i * Prime[j]] = -Prime[ j ] * F[i / Prime[j]];
                break;
            }
            F[i * Prime[j]] = F[i] * F[Prime[j]];
        }
    }
    for(int i = 2; i <= N; i++) {
        F[i] = (F[i] * S[i] + F[i - 1]);
        S[i] = (S[i] + S[i - 1]);
    }
    for(int i = 2; i <= N; i++) {
        S[i] = (S[i] + S[i - 1]);
    }
}

int Sum(int n) {
    return S[n << 1] - (S[n] << 1);
}

unsigned int AC(int n) {
    unsigned int Ans = 0;
    for(int l = 1 , r; l <= n; l = r + 1) {
        r = n / (n / l);
        Ans += (F[r] - F[l - 1]) * Sum(n / l);
    }
    return Ans;
}

int main() {
   	scanf("%u%u%u" ,&T ,&N ,&K);
    Get_Function(N << 1);
    while(T--) {
    	scanf("%u" ,&n);
    	printf("%u\n" ,AC(n));
	}
    return 0;
}