洛谷 提高+/省选- P1445 [Violet]樱花

洛谷 提高+/省选- P1445 [Violet]樱花

• $acwing$学习的樱花总结一下。
• Tip：推公式+线性筛+分解质因数。

思路： 推公式$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$ $\Rightarrow$ $\frac{x+y}{xy}=\frac{1}{n!}$ $\Rightarrow$ $xy$ = $xn!+yn!$ $\Rightarrow$ $(x-n!)y=xn!$ $\Rightarrow$ $y=\frac{xn!}{x-n!}$ $\Rightarrow$ $y=\frac{(x-n!+n!)n!}{x-n!}$ = $n!+\frac{n{!}^2}{x-n!}$ 推完。由$n!$是常数，且题目要求为正整数解，所以所有$n{!}^2$的约数都是一种方案。那么题目就转化成了统计$n{!}^2$的约数个数。所以我们需要$n!$的所有质因子个数统计出来。设质因子个数为$x1、x2、x3...$ 那么方案数就是$(x1+1)$$(x2+1)$$(x3+1)...$ 那么显然$n{!}^2$的方案数为$(x1\ast 2+1)$$(x2\ast 2+1)$$(x3\ast 2+1)...$

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=1e6+10;
const int mod=1e9+7;
int cnt;
int a[N];
int res[N];
bool st[N];
int primes[N];
void get_prime(int x){
    for(int i=2;i<=x;i++){
        if(!st[i])primes[cnt++]=i;
        for(int j=0;primes[j]*i<=x;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}
signed main(){
    int n;
    cin>>n;
    get_prime(n);
    int ans=1;
    for(int i=0;i<cnt;i++){
        int s=0;
        for(int j=n;j;j/=primes[i]){
            s+=j/primes[i];
        }
        ans=ans*(s*2+1)%mod;
    }
    cout<<ans<<endl;
    return 0;
}