M_sea

洛谷1445 [Violet]樱花
题目描述求方程 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$ 的正整数解的组数,其...
扫描右侧二维码阅读全文
31
2018/07

洛谷1445 [Violet]樱花

题目描述

求方程 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$ 的正整数解的组数,其中$N\leq 10^6$。

解的组数,应模$10^9+7$。

传送门

算法

这是一道数论题。

将原方程做出以下变化:

将方程左边通分,得:

$$\frac{x+y}{xy}=\frac{1}{n!}$$

十字相乘,得:

$$n!(x+y)=xy$$

移项,得:

$$xy-n!(x+y)=0$$

两边同时加上$(n!)^2$,得:

$$(n!)^2-n!(x+y)+xy=(n!)^2$$

左边因式分解,得:

$$(x-n!)(y-n!)=(n!)^2$$

设$a=x-n!$,$b=y-n!$,则有:

$$ab=(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}$$

也就是说:

$$ab=p_1^{2c_1}\times p_2^{2c_2} \times ... \times p_k^{2c_k}$$

因为$n!$是确定的,所以确定了$a$、$b$,就能确定$x$、$y$。

而且只要确定了$a$,就能确定$b$。

我们知道,$a$是$(n!)^2$的因式。

那么$a$的个数为:

$$(2c_1+1)(2c_2+1)...(2c_k+1)$$

那么最后的答案即为:

$$(2c_1+1)(2c_2+1)...(2c_k+1)\ mod\ 10^9+7$$

筛法筛一遍,然后把$c_i$全部计算出来,最后统计答案即可。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

const int MOD=1e9+7;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n;
int v[10000010];
int prime[10000010];
int s=0;

inline void Get_Prime() {
    for (re int i=2;i<=n;i++) {
        if (!v[i]) v[i]=i,prime[++s]=i;
        for (re int j=1;j<=s;j++) {
            if (prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
        }
    }
}

int c[10000010];

mainint main() {
    n=read(); Get_Prime();
    for (re int i=1;i<=s;i++) {
        int P=prime[i];
        for (re int j=P;j<=n;j*=P) c[i]+=(n/j);
        c[i]%=MOD;
    }
    int ans=1;
    for (re int i=1;i<=s;i++) ans=(ans*(c[i]<<1|1))%MOD;
    printf("%lld\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 54 PM

发表评论