【洛谷P1445】[Violet]樱花（唯一分解定理）

做了题还是忍不住要写一发题解&＃xff0c;感觉楼下的不易懂啊。
本题解使用latex纯手写精心打造。

题意&＃xff1a;求\(\frac{1}{x}&＃43;\frac{1}{y}&＃61;\frac{1}{n!}\)的正整数解总数。

首先&＃xff0c;不会线筛素数的先去做下LuoguP3383。

开始推导。

\[\frac{1}{x}&＃43;\frac{1}{y}&＃61;\frac{1}{n!}\]

那么\(\frac{1}{x}\)和\(\frac{1}{y}\)肯定是小于\(\frac{1}{n!}\)的。所以\(x\)和\(y\)肯定都是大于\(n!\)的。

我们令
\[y&＃61;n!&＃43;k(k∈N^*)\]
原式变为
\[\frac{1}{x}&＃43;\frac{1}{n!&＃43;k}&＃61;\frac{1}{n!}\]
等式两边同乘\(x*n!*(n!&＃43;k)\)得
\[n!(n!&＃43;k)&＃43;xn!&＃61;x(n!&＃43;k)\]
移项得
\[n!(n!&＃43;k)&＃61;x(n!&＃43;k)-xn!&＃61;xk\]
∴
\[x&＃61;\frac{n!(n!&＃43;k)}{k}&＃61;\frac{(n!)^2}{k}&＃43;n!\]
∵\(x\)为正整数

∴\(\frac{(n!)^2}{k}&＃43;n!\)为正整数&＃xff0c;\(\frac{(n!)^2}{k}\)为正整数,因为\(k&＃61;y-n!\)&＃xff0c;而\(y\)是可以取到任意正整数的&＃xff0c;所以\(k\)也可以取到任意正整数&＃xff0c;所以这道题就变成了求\((n!)^2\)的约数个数。

求约数个数&＃xff0c;线筛的时候我们已经预处理出每个数的最小质因子&＃xff0c;直接\(for\)一遍\(1-n\)&＃xff0c;不断除以它的最小公约数&＃xff0c;直到变成1为止&＃xff0c;同时每次都使记录质因数的指数的数组&＃43;&＃43;&＃xff0c;这就完成了对每个数分解质因数&＃xff0c;最后把这些质因数的指数&＃43;1乘起来就行了。时间复杂度\(O(nlogn)\)

#include
#include
#include
#include
#include
#define rep(i,m,n) for(int i&＃61;m;i<&＃61;n;&＃43;&＃43;i)
#define dop(i,m,n) for(int i&＃61;m;i>&＃61;n;--i)
#define lowbit(x) (x&(-x))
#define INF 2147483647
using namespace std;
inline int read(){int s &＃61; 0, w &＃61; 1;char ch &＃61; getchar();while(ch <&＃39;0&＃39; || ch > &＃39;9&＃39;){if(ch &＃61;&＃61; &＃39;-&＃39;)w &＃61; -1;ch &＃61; getchar();}while(ch >&＃61; &＃39;0&＃39; && ch <&＃61; &＃39;9&＃39;) s &＃61; s * 10 &＃43; ch - &＃39;0&＃39;,ch &＃61; getchar();return s * w;
}
const int MAXN &＃61; 1000010;
const int MOD &＃61; 1000000007;
int n;
int c[MAXN], v[MAXN], prime[MAXN], cnt;
int ans &＃61; 1;
int main(){n &＃61; read();/rep(i, 2, n){if(!v[i]){v[i] &＃61; i;prime[&＃43;&＃43;cnt] &＃61; i;}rep(j, 1, cnt){if(prime[j] > v[i] || prime[j] > n / i) break;v[i * prime[j]] &＃61; prime[j];}}///线筛rep(i, 1, n){ //求质因数指数for(int j &＃61; i; j !&＃61; 1; j /&＃61; v[j])c[v[j]]&＃43;&＃43;;}rep(i, 1, n) ans &＃61; (long long)ans * (c[i] * 2 &＃43; 1) % MOD; //long long保存中间过程&＃xff0c;既节省了时间、空间复杂度&＃xff0c;又不会溢出printf("%d\n", ans);return 0;
}