侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【数学】樱花

GabrielxD
2023-06-05 / 0 评论 / 0 点赞 / 200 阅读 / 1,305 字
温馨提示:
本文最后更新于 2023-06-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1294. 樱花 - AcWing题库


给定一个整数 nn ,求有多少正整数数对 (x,y)(x,y) 满足 1x+1y=1n!\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}

输入格式

一个整数 nn

输出格式

一个整数,表示满足条件的数对数量。

答案对 109+710^9+7 取模。

数据范围

1n1061 \le n \le 10^6

输入样例:

2

输出样例:

3

样例解释

共有三个数对 (x,y)(x,y) 满足条件,分别是 (3,6),(4,4),(6,3)(3,6),(4,4),(6,3)

解题

方法一:数学 线性筛 约数个数

思路

本题要求有多少对 xZ+,yZ+s.t.1x+1y=1n!x\in \mathbb{Z}^{+}, y\in \mathbb{Z}^{+} \enspace s.t. \enspace \frac{1}{x} + \frac{1}{y} = \frac{1}{n!} ,首先通分化简该式:

1x+1y=1n!y+x=xyn!xn!+yn!=xy\begin{aligned} \frac{1}{x} + \frac{1}{y} &= \frac{1}{n!} \\ y + x &= \frac{xy}{n!} \\ xn! + yn! &= xy \\ \end{aligned}

xx 表示 yy

xn!+yn!=xyxn!=xyyn!xn!=y(xn!)y=xn!xn!\begin{aligned} xn! + yn! &= xy \\ xn! &= xy - yn! \\ xn! &= y(x - n!) \\ y &= \frac{xn!}{x - n!} \end{aligned}

此时问题变为:能找到多少个 xZ+s.t.yZ+xn!xn!Z+x\in\mathbb{Z}^{+} \enspace s.t. \enspace y\in\mathbb{Z}^{+} \Rightarrow \frac{xn!}{x - n!}\in\mathbb{Z}^{+} ,变形该式:

y=xn!xn!=((xn!)+n!)n!xn!=(xn!)n!+(n!)2xn!=n!+(n!)2xn!\begin{aligned} y &= \frac{xn!}{x - n!} \\ &= \frac{((x - n!) + n!)n!}{x - n!} \\ &= \frac{(x - n!)n! + (n!)^2}{x - n!} \\ &= n! + \frac{(n!)^2}{x - n!} \end{aligned}

因为 n{n1n106,nZ+}n \in \{n | 1\le{n}\le10^6, n \in \mathbb{Z}^{+}\} ,所以只用保证 (n!)2xn!\frac{(n!)^2}{x - n!} 即可,也就是要保证 xn!(n!)2x-n! \mid (n!)^2

那么 xn!x-n! 有没有可能小于等于 00 呢?

xn!0x-n! \le 0 时, xn!x \le n! ,由 1x+1y=1n!1y=1n!1x\frac{1}{x} + \frac{1}{y} = \frac{1}{n!} \Rightarrow \frac{1}{y} = \frac{1}{n!} - \frac{1}{x} 可知,当 xn!x \le n!1x1n!1n!1x01y0\frac{1}{x} \ge \frac{1}{n!} \Rightarrow \frac{1}{n!} - \frac{1}{x} \le 0 \Rightarrow \frac{1}{y} \le 0 ,与 yZ+y \in \mathbb{Z}^{+} 矛盾,所以 xn!>0x - n! > 0

综上:我们需要找到有多少个 xZ+x\in\mathbb{Z}^{+} 使得 xn!(n!)2x-n! \mid (n!)^2 ,也就是要算出 (n!)2(n!)^2 的(正整数)约数个数。

(n!)2(n!)^2 的约数个数可以先用线性筛筛出范围 [1,n][1, n] 之间的质数,然后借助勒让德定理求出 n!n! 的质因数分解中,每个质数的次数(指数)。

根据算术基本定理n!n! 可以质因数分解为:n!=p1α1×p2α2××pkαkn! = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k} ;那么 (n!)2(n!)^2 就可以分解为:

(n!)2=p12α1×p22α2××pk2αk(n!)^2 = p_1^{2\alpha_1} \times p_2^{2\alpha_2} \times \cdots \times p_k^{2\alpha_k}

此时 (n!)2(n!)^2 的约数个数为:

f((n!)2)=i=1k(2αi+1)=(2α1+1)(2α2+1)(2αk+1)f((n!)^2) = \prod_{i=1}^{k}{(2\alpha_i + 1)} = (2\alpha_1 + 1)(2\alpha_2 + 1) \cdots (2\alpha_k + 1)

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = (int) 1e6 + 10,  MOD = (int) 1e9 + 7;
    static int[] primes = new int[N];
    static int cnt;
    static boolean[] np = new boolean[N];

    static void sieve(int n) {
        for (int x = 2; x <= n; ++x) {
            if (!np[x]) primes[cnt++] = x;
            for (int i = 0; primes[i] <= n / x; ++i) {
                np[primes[i] * x] = true;
                if (x % primes[i] == 0) break;
            }
        }
    }

    static int count(int n, int p) {
        int res = 0;
        while (n > 0) res += n /= p;
        return res;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); int n = (int) in.nval;
        sieve(n);
        long ans = 1L;
        for (int i = 0; i < cnt; ++i) {
            ans = ans * (2 * count(n, primes[i]) + 1) % MOD;
        }
        System.out.println(ans);
    }
}

0

评论区