E - Sum of gcd of Tuples (Hard)

题意

${\sum }_{a_1=1}^K{\sum }_{a_2=1}^K...{\sum }_{a_N=1}^{K}gcd(a_1,a_2,...,a_N)(mod1e9+7)$∑a1​=1K​∑a2​=1K​...∑aN​=1K​gcd(a1​,a2​,...,aN​) (mod1e9+7)

思路

1. 莫比乌斯反演(不会可以参考zdragon）
2. 简单容斥

这里讲一下简单容斥的做法吧因为笔者目前还不会莫比乌斯反演 。
令 $f\left[i\right]$f[i]为以 $i$i为 $gcd$gcd的个数，枚举 $i$i， f[i]=⌊ik​⌋n−f[i∗2]−f[i∗3]...−f[(i∗t)(<=n)]即
$f\left[i\right]={\lfloor \frac{K}{i}\rfloor }^N-{\sum }_{j>i,i\mid j}f\left[j\right]$f[i]=⌊iK​⌋N−∑j>i,i∣j​f[j]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

long long n,k,f[N];

ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	ll ans=0;
	for(int i=k;i>=1;i--){
		f[i]=power(k/i,n);
		for(int j=2*i;j<=k;j+=i) f[i]-=f[j];
		ans=(ans+i*f[i]%mod)%mod;//大小×个数才是该数所有的和
	}
	cout<<(ans+mod)%mod<<'\n';
	return 0;
}