「Luogu P1445」「Violet」樱花

Descripion

求不定方程

正整数解 $(x, y) $ 的数目,答案对 $10^9+7$ 取模。

Source

[Luogu]P1445

Solution

题目所给的方程一看就知道不能直接做,必须化简。

我们先把等式左边通分,得到

对角相乘,得到

移项

根据等式的性质,两边同时加上 $(n!)^2$,得到

这时我们发现等式左边可以因式分解了,式子变为

即使到了这一步,还是看不出什么,我们考虑换元。假设 $a=x-n!$,$b=y-n!$,则能得到

很显然 $n!$ 是确定的,$a,b$ 有多少不同的正整数解, $x,y$ 就有多少不同的值能使等式成立,而 $a,b$ 都是 $(n!)^2$ 的因数,所以问题就变为求 $(n!)^2$ 的因数个数。根据 唯一分解定理

其中 $m$ 表示 $n!$ 分解出的不同质数的个数,$p_i$ 表示 $n!$ 分解出的质数,$a_i$ 表示质因子 $p_i$ 的个数,那么

$(n!)^2$ 的因数个数就等于 $\prod\limits_{i=1}^{m}(2a_i+1)$ 。

这个东西怎么求呢?

我们先用 线性筛法(欧拉筛)求出 $1\sim n$ 内的质数,并记录下每个数的最小质因子(线性筛中的合数只会被它的最小质因子筛去)。因为我们要求 $n!$ 的质因数,所以枚举 $1 \sim n$ 每一个数,依次分解它们,得到它们有哪些质因数。具体方法:每次除以它本身的最小质因子,直到这个数变成 $1$ 为止。例如求 $18$ 的因数:$18$ 的最小质因子是 $2$,就将 $a_2 +1$,$18$ 除以 $2$ 变为 $9$;再考虑 $9$,$9$ 的最小质因子是 $3$,将 $a_3 +1$,$9$ 除以 $3$ 变为 $3$;$3$ 的最小质因子是 $3$,所以将 $a_3 + 1$,$3$ 除以 $3$ 变为 $1$,停止计算 。此时我们已经可以知道:$18=2^{a_2=1}\times 3^{a_3=2} $。按上述操作处理,就能算出 $n!$ 的质因数分布,根据公式就能得到答案。同时因为最小的质数是 $2$,每次除以它的最小质因子时,最大也会变为原来的 $\frac{1}{2}$,所以时间复杂度为 $O(n\log n)$ 。

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e6;
const LL MOD = 1e9 + 7;
int n, cnt, a[MAXN + 5], prime[MAXN + 5], minPrime[MAXN + 5];
//minPrime[i]表示 i 的最小质因子
LL ans = 1;

inline void getPrime(int n) {
for (int i = 2; i <= n; ++i) {
if (!minPrime[i]) {
minPrime[i] = i;//质数的最小质因子是它本身
prime[++cnt] = i;
}
for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
minPrime[i * prime[j]] = prime[j];//线性筛中的合数只会被最小质因子筛去
if (i % prime[j] == 0) break;
}
}
}

int main() {
read(n);
getPrime(n);//线性筛质数
for (int i = 1; i <= n; ++i)
for (int j = i; j > 1; j /= minPrime[j])
++a[minPrime[j]];//质因子计数
for (int i = 1; i <= cnt; ++i)
ans = ans * (LL) (a[prime[i]] << 1 | 1) % MOD;//用公式求得答案
write(ans);
putchar('\n');
return 0;
}

本文标题:「Luogu P1445」「Violet」樱花

文章作者:Heartlessly

发布时间:2019年04月02日 - 10:17:53

最后更新:2019年04月27日 - 15:48:01

原始链接:https://heartlessly.github.io/problems/luogu-p1445/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%