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

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

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

思路： 推公式$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$ $?$ $\frac{x+y}{xy}=\frac{1}{n!}$ $?$ $xy$ = $xn!+yn!$ $?$ $(x?n!)y=xn!$ $?$ $y=\frac{xn!}{x?n!}$ $?$ $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?2+1)$$(x2?2+1)$$(x3?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;
}