bzoj 2721: [Violet 5]樱花

题意

给你$n$
询问有多少个数对$(x,y)$
使得$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$

题解

感觉这题还挺好玩的
提供两个做法吧

一般来说，先同分一下可以得到
$xy=n!(x+y)$
这种式子，一般都是通过提取$d=(x,y)$来化简
这题也可以这么做，那么可以变成
$d{x}^{\prime }{y}^{\prime }=n!(x^{\prime }+y^{\prime })$
可以发现$(x^{\prime }+y^{\prime },x^{\prime })=1,(x^{\prime }+y^{\prime },y^{\prime })=1$
那么可以得到
$(x^{\prime }+y^{\prime })|d$
设$d=k(x^{\prime }+y^{\prime })$
代进去就是$k{x}^{\prime }{y}^{\prime }=n$
可以发现，等价于求互质对数$(x^{\prime },y^{\prime })$的数量
把n分解质因数之后就可以DP来做了
可以化为一般的式子

还有一个很神奇的做法
可以发现,$x>n!,y>n!$
那么就直接设$y=n!+d$
丢进去就是
$x(n!+d)=n!(x+n!+d)$
把括号打开，可以发现，每一个d对应一个x，y
然后就变成求$(n!{)}^2$的因子数了23333
怎么感觉这么神奇啊

然后直接算因子数就好了
虽然这个数很大，但是质因数还是$10^5$级别，暴力算就行了

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1000005;
const int MOD=1e9+7;
int add (int x,int y)   {
    x=x+y;return x>=MOD?x-MOD:x;}
int mul (int x,int y)   {
    return (LL)x*y%MOD;}
int dec (int x,int y)   {
    x=x-y;return x<0?x+MOD:x;}
int Pow (int x,int y)
{
    if (y==1) return x;int lalal=Pow(x,y>>1);lalal=mul(lalal,lalal);if (y&1) lalal=mul(lalal,x);return lalal;
}
int n;
bool vis[N];
int pri[N],tot;
void Init ()
{
    memset(vis,false,sizeof(vis));for (int u=2;u<=n;u++){
    if (vis[u]==false)	pri[++tot]=u;for (int i=1;i<=tot;i++){
    int j=pri[i];if (n/u<j) break;vis[j*u]=true;if (u%j==0) break;}}
}
int main()
{
    scanf("%d",&n);Init();int ans=1;for (int u=1;u<=tot;u++){
    int x=pri[u];int lalal=0;for (int i=1;i<=n/x;i*=x)	lalal=lalal+n/(i*x);lalal=add(lalal,lalal);lalal=add(lalal,1);ans=mul(ans,lalal);}printf("%d\n",ans);return 0;
}