Arcoder abc162E.Sum of gcd of Tuples (Hard)

题目链接

思路

考虑对于从 1 1 1到 k k k每一个值对答案的贡献。那么就要记录对于 1 1 1到 k k k，每一个 g c d gcd gcd值为最终答案的方案数。

f [ i ] : g c d ( a 1 , a 2 , . . . , a n ) = i f[i]:gcd(a_1,a_2,...,a_n)=i f[i]:gcd(a1​,a2​,...,an​)=i时的方案数。

考虑到这个数至少是 i i i，那么在 k k k个数中可以是i的倍数的数只有 k / i k/i k/i个，所以最多是 k i n \frac{k}{i}^n ik​n种方案。那么这样计算过程中会把 i i i的倍数的那些方案也会算进去，所以需要减去关于 i i i的倍数的方案数。即减去 k 2 ∗ i n , k 3 ∗ i n . . . \frac{k}{2*i}^n,\frac{k}{3*i}^n... 2∗ik​n,3∗ik​n...等方案数。相当于 g c d gcd gcd值为 i i i时的方案数变成了

f [ i ] = k i n − f [ i ∗ 2 ] − f [ i ∗ 3 ] − . . . ( i ∗ m ≤ k , m ∈ N + 且 m > 1 ) f[i]=\frac{k}{i}^n-f[i*2]-f[i*3]-...(i*m\leq k,m\in N^+且m>1) f[i]=ik​n−f[i∗2]−f[i∗3]−...(i∗m≤k,m∈N+且m>1).

因此在预处理的时候从 k k k到 1 1 1的顺序处理即可.最后计算每一个gcd的答案贡献值即可.

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
#define gcd __gcd
const int mod = 1e9 + 7;

LL f[N], d[N];

LL kpow(LL a, LL n) {
	LL res = 1;
	while(n) {
		if(n & 1) res = res * a % mod;
		n >>= 1;
		a = a * a % mod;
	}
	return res;
}

void solve() {
	int n, k;
	scanf("%d%d", &n, &k);
	LL res = 0;
	for(int i = k; i >= 1; i--) {
		f[i] = kpow(k / i, n);
		LL cnt = 0;
		for(int j = i + i; j <= k; j += i) {
			cnt = (cnt + f[j]) % mod;
		}
		f[i] = (f[i] - cnt + mod) % mod;
		res = (res + f[i] * i % mod) % mod;
	}
	printf("%lld\n", res);
}

int main() {
	// freopen("in.txt", "r", stdin);
	// int t; cin >> t; while(t--)
	solve();
	return 0;
}