redux工作原理讲解及使用方法
970 2023-04-03 05:15:57
题目传送门
做了这题,感觉这类题目的大多数分析过程都是这样的:
∵\(x,y∈Z^+\)
∴\(x>n!\) \(y>n!\) 小学数学知识~
转换为y
的表示式
变形
\[xn!+yn!=xy\]继续变形
\[xn!=y(x-n!)\] \[y=\frac{xn!}{x-n!}\]经典的变形技巧:
\[y=\frac{(x-n!+n!)n!}{x-n!}\] \[y=\frac{(x-n!)n!+n!^2}{x-n!}\] \[y=n! + \frac{n!^2}{x-n!}\]因为上面已经证明了\(x-n!>0\)的,所以要想\(y\)有正整数解,则必然需要
\[(x-n!)|n!^2\]换句话说,就是\(n!^2\)有多少个约数,就有相应的正整数\(x\),也就有一个对应的\(y\)。
如果我们能够求得\(n!^2\)的约数个数,也就是\({x,y}\)的匹配对数。
for (int i = 0; i < cnt; i++) { int p = primes[i]; int s = 0; for (int j = n; j; j /= p) s += j / p; printf("%d %d\n", p, s); }
求\(n!^2\)一共有多少个约数
假设$$n!=P_1^{c_1} \times P_2^{c_2}\times ...\times P_k^{c_k}$$
则$$n!2=P_1{2c_1}\times P_2^{2c_2}\times ...\times P_k^{2c_k}$$
根据约数个数定理
知道约数的个数是\((2c_1+1)\times (2c_2+1)\times …\times (2c_k+1)\)
#include <bits/stdc++.h>using namespace std;typedef long long LL;const int mod = 1e9 + 7;//欧拉筛const int N = 1e6 + 10;int primes[N], cnt; // primes[]存储所有素数bool st[N]; // st[x]存储x是否被筛掉void get_primes(int n) { memset(st, 0, sizeof st); cnt = 0; for (int i = 2; i <= n; i++) { if (!st[i]) primes[cnt++] = i; for (int j = 0; primes[j] * i <= n; j++) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } }}int main() { int n; cin >> n; //步骤1:筛质数 get_primes(n); //步骤2:阶乘质因子分解 int res = 1; for (int i = 0; i < cnt; i++) { int p = primes[i]; int s = 0; for (int j = n; j; j /= p) s += j / p; //步骤3:约数个数公式 res = (LL)res * (2 * s + 1) % mod; } cout << res << endl; return 0;}
数学公式推导
转化为一个自变量,一个因变量的形式,最终描述:有一个\(x\),就能确定一个\(y\),需要满足xxx
条件(一般是谁能整除谁之类,转化为求约数个数)
唯一分解定理
阶乘的质因子分解
经典作法,除了背下来,多看几遍,还有啥更好的办法~
约数和公式