难度： 蓝（我不理解为什么是蓝）
算法： 数论，筛子
求以下方程的正整数解的个数。
通分，得到：
进行变形：
因为 x,yx,yx,y 都是正整数且必须大于 n!n!n!，那么求解的个数就相当于求 (n!)2(n!)^2(n!)2 的因子个数。我们知道：
一个数的因子个数相当于其每个质因子的次数 +1+1+1 之积。
先用筛子筛出 nnn 以内的每个质数，对于每个质数，求它在 n!n!n! 中这个质因子的次数。记次数为 kkk。那么这个质因子对答案的贡献就是 2k+12k+12k+1 。最后把贡献乘起来。
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,p[1000100],k,c,ans=1; int main(){ scanf("%lld",&n); for(ll i=2;i<=n;i++){ if(!p[i]){ for(int j=i+i;j<=n;j+=i) p[j]=1; } } for(ll i=2;i<=n;i++){ if(p[i]) continue; k=n,c=1; while(k){ k/=i; c+=2*k; } ans=(ans*c)%int(1e9+7); } printf("%lld",ans); }
By signing up a HFOJ universal account, you can submit code and join discussions in all online judging services provided by us.
Using your HFOJ universal account
C20250073
LV 8
@ 1 year ago
