題目描述
給下N,M,K.求
輸入
輸入有多組資料，輸入資料的第一行兩個正整數T,K，代表有T組資料，K的意義如上所示，下面第二行到第T+1行，每行為兩個正整數N,M，其意義如上式所示。
輸出
如題
樣例輸入
1 2
3 3
樣例輸出
20
題解
莫比烏斯反演+線性篩
$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\gcd(i,j)^k\\=\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=d]\\=\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac md\rfloor}[\gcd(i,j)=1]\\=\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac md\rfloor}\sum\limits_{t|gcd(i,j)}\mu(t)\\=\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac md\rfloor}\sum\limits_{t|i\&t|j}\mu(t)\\=\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{t=1}^{\lfloor\frac{\min(n,m)}d\rfloor}\mu(t)\lfloor\frac n{dt}\rfloor\lfloor\frac m{dt}\rfloor$
繼續令$D=dt$，可以得到：
$\sum\limits_{d=1}^{\min(n,m)}d^k\sum\limits_{t=1}^{\lfloor\frac{\min(n,m)}d\rfloor}\mu(t)\lfloor\frac n{dt}\rfloor\lfloor\frac m{dt}\rfloor\\=\sum\limits_{D=1}^{\min(n,m)}\lfloor\frac nD\rfloor\lfloor\frac mD\rfloor\sum\limits_{d|D}d^k\mu(t)\\=\sum\limits_{D=1}^{\min(n,m)}\lfloor\frac nD\rfloor\lfloor\frac mD\rfloor f(D)\\(f(D)=\sum\limits_{d|D}d^k\mu(t))$
此時可以選擇通過枚舉倍數來預處理$f$數組，有個小優化：枚舉時先枚舉$t$，如果$\mu(t)=0$則不進行操作。這樣預處理的時間複雜度為$O(n\ln n+n\log k)$，可以勉強通過本題。
然後我就被CQzhangyu大佬D了一頓= =
此時可以發現$f$是$id^k$與$\mu$的狄利克雷卷積，兩個積性函數的狄利克雷卷積也是積性函數。于是可以快篩$f$函數。
當$i$為質數時，顯然 $f(i)=i^k-1$
考慮 $i*p$ （p是質數）的處理：
當 $i\mod p\neq 0$ 時，顯然$i$與$p$互質，就有$f(i*p)=f(i)*f(p)$
當 $i\mod p=0$ 時，對$f(i*p)$有影響的$t$一定是與對$f(i)$有影響的$t$中，因為其餘的因數都至少包含$p^2$，$\mu=0$。而此時$d$增加了$p$倍，故$f(i*p)=f(i)*p^k$。
綜上可以線性篩出$f$函數，然後分塊處理。時間複雜度為$O(n+\frac{n\log k}{\ln n}+T\sqrt n)$
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 5000010
using namespace std;
typedef long long ll;
const int p = 5000000 , mod = 1000000007;
int prime[N] , tot;
ll d[N] , f[N] , sum[N];
bool np[N];
ll pow(ll x , ll y)
{
ll ans = 1;
while(y)
{
if(y & 1) ans = ans * x % mod;
x = x * x % mod , y >>= 1;
}
return ans;
}
int main()
{
int T , k , i , j , n , m;
ll ans;
scanf("%d%d" , &T , &k);
f[1] = sum[1] = 1;
for(i = 2 ; i <= p ; i ++ )
{
if(!np[i]) prime[++tot] = i , d[tot] = pow(i , k) , f[i] = (d[tot] - 1 + mod) % mod;
for(j = 1 ; j <= tot && i * prime[j] <= p ; j ++ )
{
np[i * prime[j]] = 1;
if(i % prime[j] == 0)
{
f[i * prime[j]] = f[i] * d[j] % mod;
break;
}
else f[i * prime[j]] = f[i] * f[prime[j]] % mod;
}
sum[i] = (sum[i - 1] + f[i]) % mod;
}
while(T -- )
{
scanf("%d%d" , &n , &m) , ans = 0;
for(i = 1 ; i <= n && i <= m ; i = j + 1)
j = min(n / (n / i) , m / (m / i)) , ans = (ans + (ll)(n / i) * (m / i) % mod * (sum[j] - sum[i - 1] + mod)) % mod;
printf("%lld\n" , ans);
}
return 0;
}
轉載于:https://www.cnblogs.com/GXZlegend/p/7289240.html