标签：樱花 Violet5 begin frac int therefore end aligned

[Violet5]樱花题解

题意概括：

题目意思很明白，输入一个\(int\)类型整数\(n\) ( \(1<=n<=10^6\) ) 求方程 \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}\) ( \(n!\) 表示 \(n\) 的阶乘，即 \(n!=1\times2\times3\times······\times n\) ) 解的个数

题目分析：

肯定是一个数论题(废话)，题目中的方程直接枚举是 \(O(n^3)\) 的时间复杂度，绝对会 \(TLE\) ，那么就只能用魔法打败魔法，用math知识对方程进行分析：

\[\begin{aligned} & \frac{1}{x} + \frac{1}{y} = \frac{1}{n!}\\ & 设 n!=k，\\ \end{aligned} \]

第一眼看上去，\(x\) 和 \(y\) 都是一次的整数，只有 \(n!\) 是一个式子，所以用一个未知数代替，方便运算和思考。其实就是我懒对原方程进行化简，我习惯把 \(x\) 当作主元，用 \(y\) 也可以。把 \(y\) 和 \(k\) 当作一个常数，用解普通方程的步骤去解。

\[\begin{aligned} & \therefore \frac{1}{x} + \frac{1}{y} = \frac{1}{k}\\ & \frac{1}{x} = \frac{1}{k} - \frac{1}{y}\\ & \frac{1}{x} = \frac{y}{ky} - \frac{k}{ky}\\ & \frac{1}{x} = \frac{y-k}{ky}\\ & x = \frac{ky}{y-k}\\ \end{aligned} \]

这时，无法对方程继续化简，但分式上下都有 \(y\) 和 \(k\) ，所以可以考虑再设一个关于 \(y\) 和 \(k\) 的未知数，去表达 \(y\) 和 \(k\) 的关系。

\[\begin{aligned} & 设 y-k = p，\\ & \therefore y = k + p\\ \end{aligned} \]

找到之后，就可以把 \(y=k+p\) 代入方程，得到

\[\begin{aligned} & \therefore x = \frac{k(k+p)}{p}\\ & \therefore x = k+\frac{k^2}{p}\\ \end{aligned} \]

解出 \(x\) 的值后，观察式子，发现可以运用文化课上讲过的整数的性质，

\[\begin{aligned} & \because x，k=n!为正整数\\ & \therefore p \mid k^2\\ & \therefore y-n! \mid (n!)^2\\ & \therefore (y-n!) 为(n!)^2的因子\\ & \therefore (y-n!) 为n!的因子\\ & \because y，n!为正整数\\ & \therefore x为正整数\\ & \therefore 只要(y-n!)为n!的因子，就有原方程的一组解\\ \end{aligned} \]

通过分析，就可以把原问题转化为求\(n!\)的因子数

代码实现

由唯一分解定理，我们只需要解出n!的质因数，balabala的一个埃氏筛函数

int primes[1000005];//记录质因数
bool st[1000005];//标记是否为质数
int cnt;
int n;
long long ans=1;
void prime_set(int n){
    st[1]=1;
    for (int i=2;i<=n;i++){
        if (!st[i])
            primes[++cnt]=i;
        for (int j=1;j<=cnt&&primes[j]*i<=n;j++){
            st[primes[j]*i]=1;
            if (i%primes[j]==0){
                break;
            }
        }
    }
}

通过唯一分解定理的另一个公式，即
\(n的因子数=\prod\limits_{i=0}^{质因子个数}质因子i的个数+1\)
就可以得到答案了

prime_set(n);
for (int i = 1; i <= cnt; i++){
    int s = 0;
    for (int j=n;j;j/=primes[i]){
        s+=j/primes[i];
    }
    ans=1ll*ans*(s<<1|1)%P;//1ll用来防止数据溢出
}
printf("%lld",ans);

Code

#include<bits/stdc++.h>
#define P 1000000007
using namespace std;
int primes[1000005];
bool st[1000005];
int cnt;
int n;
long long ans=1;
void prime_set(int n){
    st[1]=1;
    for (int i=2;i<=n;i++){
        if (!st[i])
            primes[++cnt]=i;
        for (int j=1;j<=cnt&&primes[j]*i<=n;j++){
            st[primes[j]*i]=1;
            if (i%primes[j]==0){
                break;
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    prime_set(n);
    for (int i = 1; i <= cnt; i++){
        int s = 0;
        for (int j=n;j;j/=primes[i]){
            s+=j/primes[i];
        }
        ans=1ll*ans*(s<<1|1)%P;
    }
    printf("%lld",ans);
    return 0;
}

标签：樱花,Violet5,begin,frac,int,therefore,end,aligned
From： https://www.cnblogs.com/z10h09x11/p/17646513.html