求不定方程 \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}\) 的正整数解 \((x,y)\) 的对数。
一个整数 \(n\)。
一个整数，表示有多少对 \((x,y)\) 满足题意。答案模 \(10^9+7\)
2
3
\(30\%\) 满足 \(n \leq 100\)\(100 \%\) 满足 \(n \leq 10^6\)
推一推就出来啦~ 不妨设 \(x \leq y\) 原方程变形可得 \(y=\frac{n!x}{n!-x}\) 设 \(z=n!-x\) ，则 \(y=\frac{n!(n!-z)}{z}\) 要求 \(y\) 为整数，所以 \(z \mid n!(n!-z)\)
对 \(z\) 分两种情况讨论：
\(z \mid n!\) 那没得说\(z\not\mid n!\) ：设 \((n!,z)=g1\) , 那么 \(\frac{z}{g1} \mid (n!-z)\) 又因为 \(\frac{z}{g1} \mid z\) ，所以 \(\frac{z}{g1} \mid n!\) ，即 \(z \mid (n!)^2\)于是这道题就是求 \((n!)^2\) 的约数个数，分解质因数，然后指数加一连乘。
又 \(get\) 到了新技能（虽然不是第一次了）：分解质因数更快的技巧——线性筛素数，记下每个数最小质因子的序号。
#include<cstdio> #include<iostream> #include<algorithm> #define Mod 1000000007 using namespace std; const int N = 1000005; typedef long long ll; int n,m; int p[N],pnum,prime[N],mn[N]; void getp(){ for(int i=2;i<=n;i++) p[i]=1; for(int i=2;i<=n;i++){ if(p[i]) prime[pnum++]=i,mn[i]=pnum-1; for(int j=0;j<pnum && (ll)prime[j]*i<=n;j++){ p[prime[j]*i]=0; mn[prime[j]*i]=j; if(i%prime[j]==0) break; } } } int c[N]; void cal(int x){ while(x!=1){ c[mn[x]]++; x/=prime[mn[x]]; } } int main() { scanf("%d",&n); getp(); for(int i=2;i<=n;i++) cal(i); int ans=1; for(int i=0;i<pnum;i++) ans=((ll)ans*(c[i]*2+1))%Mod; printf("%d\n",ans); return 0; }转载于:https://www.cnblogs.com/lindalee/p/9846170.html
