Product
题目链接：luogu P5221
题目大意
求 ∏ i = 1 n ∏ j = 1 n lcm ( i , j ) gcd ? ( i , j ) \prod\limits_{i=1}^n\prod\limits_{j=1}^n\dfrac{\text{lcm}(i,j)}{\gcd(i,j)} i=1∏n?j=1∏n?gcd(i,j)lcm(i,j)? 模 104857601 104857601 104857601 的值。
思路
直接开始化简式子：
首先有
lcm
(
i
,
j
)
=
i
j
gcd
?
(
i
,
j
)
\text{lcm}(i,j)=\dfrac{ij}{\gcd(i,j)}
lcm(i,j)=gcd(i,j)ij? 就有
∏
i
=
1
n
∏
j
=
1
n
i
j
gcd
?
(
i
,
j
)
2
\prod\limits_{i=1}^n\prod\limits_{j=1}^n\dfrac{ij}{\gcd(i,j)^2}
i=1∏n?j=1∏n?gcd(i,j)2ij?：
∏
i
=
1
n
∏
j
=
1
n
i
j
∏
i
=
1
n
∏
j
=
1
n
gcd
?
(
i
,
j
)
?
2
\prod\limits_{i=1}^n\prod\limits_{j=1}^nij\prod\limits_{i=1}^n\prod\limits_{j=1}^n\gcd(i,j)^{-2}
i=1∏n?j=1∏n?iji=1∏n?j=1∏n?gcd(i,j)?2
(
n
!
)
2
n
∏
i
=
1
n
∏
j
=
1
n
gcd
?
(
i
,
j
)
?
2
(n!)^{2n}\prod\limits_{i=1}^n\prod\limits_{j=1}^n\gcd(i,j)^{-2}
(n!)2ni=1∏n?j=1∏n?gcd(i,j)?2
然后我们考虑统计每个
gcd
?
\gcd
gcd 的值的出现次数，然后发现：
(
n
!
)
2
n
∏
d
d
∑
i
=
1
?
n
d
?
∑
j
=
1
?
n
d
?
[
gcd
?
(
i
,
j
)
=
=
1
]
?
?
2
(n!)^{2n}\prod\limits_{d}d^{\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(i,j)==1]*-2}
(n!)2nd∏?di=1∑?dn???j=1∑?dn???[gcd(i,j)==1]??2
那这个不就是那个仪仗队什么的，直接上莫比乌斯函数即可。
然后你可以把
?
2
-2
?2 提到外面里面的搞完再乘可以快一点。
然后要注意的是次方里面是对 m o ? 1 mo-1 mo?1 取模，因为欧拉定理是模 φ ( m o ) \varphi(mo) φ(mo)，然后模数是质数所以是它减一。
代码
#include<cstdio>
#define Mo 104857601
using namespace std;
const int N = 1e6 + 100;
int n, ans, mu[N], prime[N];
bool np[N];
int cheng(int x, int y, int mo) {return 1ll * x * y % mo;}
int jia(int x, int y, int mo) {return x + y >= mo ? x + y - mo : x + y;}
int jian(int x, int y, int mo) {x = x < 0 ? x + mo : x; y = y < 0 ? y : y + mo; return x < y ? x - y + mo : x - y;}
int ksm(int x, int y, int mo) {int re = 1; while (y) {if (y & 1) re = cheng(re, x, mo); x = cheng(x, x, mo); y >>= 1;} return re;}
void Init() {
mu[1] = 1;
for (int i = 2; i <= n; i++) {
if (!np[i]) mu[i] = -1, prime[++prime[0]] = i;
for (int j = 1; j <= prime[0] && i * prime[j] <= n; j++) {
np[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
mu[i * prime[j]] = -mu[i];
}
}
for (int i = 1; i <= n; i++) mu[i] = mu[i - 1] + mu[i];
}
int clac(int n) {
int re = 0;
for (int L = 1, R; L <= n; L = R + 1) {
R = n / (n / L);
re = jia(re, cheng(jian(mu[R], mu[L - 1], Mo - 1), cheng(n / L, n / L, Mo - 1), Mo - 1), Mo - 1);
}
return re;
}
int work() {
int re = 1;
for (int L = 1, R; L <= n; L = R + 1) {
R = n / (n / L);
int di = 1; for (int i = L; i <= R; i++) di = cheng(di, i, Mo);
re = cheng(re, ksm(di, clac(n / L), Mo), Mo);
}
return re;
}
int main() {
scanf("%d", &n);
Init();
ans = 1; for (int i = 1; i <= n; i++) ans = cheng(ans, i, Mo);
ans = ksm(ans, 2 * n, Mo);
int sum = work();
printf("%d", cheng(ans, ksm(cheng(sum, sum, Mo), Mo - 2, Mo), Mo));
return 0;
}
