TrickGCD

Posted on | In , ,

题目链接

题意

输入$a$数组，询问有多少个$b$数组使得：

思路

首先容易想到这题要求整个$b$数列的最大公约数大于1，简记其$gcd$为$gcd(b)$。
不妨设$F(d)$表示$d|gcd(b)$的方案数，$f(d)$表示$gcd(b)=d$的方案数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
const int N = 1e5 + 5;
int prime[10000];
int tot;
bool vis[N];
ll miu[N];
void pre(int n)
{
	tot = 0;
	miu[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		if (!vis[i])
			prime[++tot] = i, miu[i] = -1;
		for (int j = 1; j <= tot && i * prime[j] <= n; j++)
		{
			vis[i * prime[j]] = 1;
			if (i % prime[j] == 0)
			{
				miu[i * prime[j]] = 0;
				break;
			}
			miu[i * prime[j]] = -miu[i];
		}
	}
}
ll cnt[N];
int a[N];
const ll mod = 1e9 + 7;
ll f[N];
ll Pow(ll a, ll b)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1)
			ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
int main()
{
	int n;
	pre(100000);
	int T;
	scanf("%d", &T);
	for (int ks = 1; ks <= T; ks++)
	{
		int n;
		scanf("%d", &n);
		for (int i = 0; i <= 100000; i++)
			cnt[i] = 0;
		int mnv = 0x3f3f3f3f, mxv = 0;
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			mnv = min(mnv, a[i]);
			mxv = max(mxv, a[i]);
			cnt[a[i]]++;
		}
		if (mnv <= 1)
		{
			printf("Case #%d: %lld\n", ks, 0ll);
			continue;
		}
		for (int i = 1; i <= mxv; i++)
			cnt[i] = cnt[i] + cnt[i - 1];
		ll ans = 0;
		int j;
		for (int i = 0; i <= mxv; i++)
			f[i] = 0ll;
		for (int i = 2; i <= mnv; i++)
		{
			f[i] = 1ll;
			for (int l = i; l <= mxv; l += i)
			{
				//f[i] = f[i] * (cnt[min(l + i - 1, mxv)] - cnt[l - 1] + mod) % mod * (l / i) % mod;
				f[i] = f[i] * Pow(1ll * l / i, cnt[min(l + i - 1, mxv)] - cnt[l - 1]) % mod;
			}
			//dbg(i, f[i]);
			/*
			for (int j = i; j <= mxv; j++)
			{
				f[i] = f[i] * Pow(j / i, cnt[j]) % mod;
			}
			*/
		}
		for (int i = 2; i <= mnv; i++)
		{
			for (int d = i; d <= mxv; d += i)
				ans = (ans + f[d] * miu[d / i] % mod + mod) % mod;
		}
		printf("Case #%d: %lld\n", ks, ans);
	}
	return 0;
}
0%