洛谷P5221 Product 欧拉定理+欧拉函数

洛谷P5221 Product

标签

• 欧拉函数
• 欧拉定理

前言

• 无

简明题意

• 求：
  \[\prod_{i=1}^n\prod_{j=1}^n\frac {lcm(i,j)}{gcd(i,j)}(\%)\]
  
• 数据范围是1e6，时限是0.2s

思路

• 将原式中\(lcm\)用\(gcd\)表示，因此原式:
  \[\prod_{i=1}^n\prod_{j=1}^n\frac {ij}{\left(gcd(i,j)\right)^2}\]
  
  

  一般来说，\(lcm\)是没有\(gcd\)那样显然的递归式，因此\(lcm\)不好直接求，通常会将\(lcm\)转化成\(gcd\)来求\(lcm\)，而\(gcd(i,j)*lcm(i,j)=ij\),因此\(lcm(i,j)=\frac {ij}{gcd(i,j)}\)

• 运用结合律拆开：
  \[\prod_{i=1}^n\prod_{j=1}^nij*\left(\prod_{i=1}^n\prod_{j=1}^ngcd(i,j)\right)^{-2}\]
  
  

  注意,关于多重和式：在\(\sum\)中有
  \[\sum\limits_ia_i\sum\limits_jb_j=\sum\limits_ia_i*\sum\limits_jb_j\]
  而在\(\prod\)中
  \[\prod\limits_ia_i\prod\limits_j^nb_j=\prod\limits_ia_i*\left(\prod\limits_jb_j\right)^n\]
  因此在数与求和符号相乘时，\(\sum\)中乘号可以省略，在\(\prod\)中记得不要省略乘号
  
  
  
  

  分配率就是把被加\乘式中的数提到前面

• 先求\(\prod\limits_{i=1}^n\prod\limits_{j=1}^nij\)。直接分配律得：
  \[\prod\limits_{i=1}^n\left(i^n*\prod\limits_{j=1}^nj\right)=\prod\limits_{i=1}^n\left(i^n*n!\right)=(n!)^n*\prod_{i=1}^ni^n=(n!)^n*(n!)^n=(n!)^{2n}\]
  
• 第一个式子就这样解决了，现在我们去求第二个式子：\(\prod\limits_{i=1}^n\prod\limits_{j=1}^ngcd(i,j)\)，首先就改为枚举\(gcd\)，然后用值去次方一下出现的次数：
  \[\prod_{x=1}^nx^{\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)==x]}\]
  
• 后面的\(\sum\limits_{i=1}^n\sum\limits_{j=1}^n[gcd(i,j)==x]\)是不是很熟悉？他就等于\(2pre\phi([\frac nx])-1\)(这里使用欧拉函数推出来的。不清楚的同学翻一翻我在欧拉函数分类下的文章，有一篇讲过)，于是第二个式子等于：
  \[\prod_{x=1}^nx^{2pre\phi([\frac nx])-1}\]
  
• 于是总的式子就是要求：
  \[(n!)^{2n}*\left(\prod_{x=1}^nx^{2pre\phi([\frac nx])-1}\right)^{-2}\]
  
• 左边的式子快速幂\(O(nlogn)\)就能处理出来，右边的，可以提前线性筛再前缀和出来\(2pre\phi([\frac nx])-1\)，求出来了要给右边的式子求一个乘法逆元，就能求出答案了。
• 注意，这里\(x\)的指数部分我们是用数组保存起来了，而且保存的应该是真实值而不是取模后的值，因为指数是不能取模的！！不要搞混了。
• 所以，指数的真实值是会超过int的，我们只能开一个longlong保存指数，题目只给了7.8MB内存，1kb约=250个int，手算一下也会发现longlong开不下。因此我们需要对指数也取模。怎么取模？欧拉定理，只要模数是质数，在模意义下的次方运算，就可以给次方提前%上模数的欧拉函数，也就是模数-1.，然后就能AC了。

注意事项

总结

• 一般来说，\(lcm\)是没有\(gcd\)那样显然的递归式，因此\(lcm\)不好直接求，通常会将\(lcm\)转化成\(gcd\)来求\(lcm\)，而\(gcd(i,j)*lcm(i,j)=ij\),因此\(lcm(i,j)=\frac {ij}{gcd(i,j)}\)
• 运算符的规律总结：
  

  注意,关于多重和式：在\(\sum\)中有
  \[\sum\limits_ia_i\sum\limits_jb_j=\sum\limits_ia_i*\sum\limits_jb_j\]
  而在\(\prod\)中
  \[\prod\limits_ia_i\prod\limits_j^nb_j=\prod\limits_ia_i*\left(\prod\limits_jb_j\right)^n\]
  因此在数与求和符号相乘时，\(\sum\)中乘号可以省略，在\(\prod\)中记得不要省略乘号
  
  
  
  

  分配率就是把被加\乘式中的数提到前面

• 注意逆元运算，对于\(\frac ab\%p=a*inv(b\%p)\%p\)，计算逆元的那个数是可以提前取模的！！！
• \(a^b\%p\)，运算时a可以提前模p，但是b是万万不能提前模p的，而是应该运用欧拉定理。

AC代码

#include<cstdio> #include<algorithm> using namespace std; const int maxn = 1e6 + 10; const int mod = ; bool no_prime[maxn]; int prime[maxn], phi[maxn]; int shai(int n) { int cnt = 0; phi[1] = 1; for (int i = 2; i <= n; i++) { if (!no_prime[i]) prime[++cnt] = i, phi[i] = i - 1; for (int j = 1; j <= cnt && prime[j] * i <= n; j++) { no_prime[prime[j] * i] = 1; phi[prime[j] * i] = i % prime[j] == 0 ? phi[i] * prime[j] : phi[i] * (prime[j] - 1); if (i % prime[j] == 0) break; } } for (int i = 1; i <= n; i++) phi[i] = (phi[i - 1] + 2 * phi[i]) % (mod - 1); return cnt; } int ksm(int a, int b) { int ans = 1, base = a; while (b) { if (b & 1) ans = 1ll * ans * base % mod; base = 1ll * base * base % mod; b >>= 1; } return ans; } void solve() { int n; scanf("%d", &n); shai(n); int ans = 1; for (int i = 1; i <= n; i++) ans = 1ll * ans * i % mod; ans = ksm(ans, 2 * n); int tot = 1; for (int x = 1; x <= n; x++) tot = (1ll * tot * ksm(x, phi[n / x] - 1)) % mod; printf("%d", 1ll * ans * ksm(1ll * tot * tot % mod, mod - 2) % mod); } int main() { solve(); return 0; }