樱花

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1070 字

求1/x+1/y=1/n!的正整数解数目，答

一本通
练习

正文

/*
原题：T1624「一本通 6.2 练习 5」樱花（HackerRank Equations）
题意：求 1/x + 1/y = 1/n! 的正整数解 (x,y) 数目，答案对 1e9+7 取模。
思路：令 N=n!，方程化为 (x-N)(y-N)=N²。正整数解个数 = N² 的正约数个数 = ∏(2e_p+1)，
其中 e_p 为质数 p 在 n! 中的指数（e_p=∑⌊n/p^k⌋）。筛出 ≤n 的质数累加即可。
复杂度：时间 O(n log log n)，空间 O(n)
易错点：1) 约数个数是 (2e+1) 的乘积而非 e+1；2) 指数求和用 ⌊n/p^k⌋ 累加；3) 乘法边乘边取模防溢出。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MOD=1000000007;
const int MAX=1000000;
vector<int> primes;
void sieve(){
    vector<bool> isp(MAX+1,true);
    isp[0]=isp[1]=false;
    for(int i=2;i<=MAX;i++){
        if(isp[i]) primes.push_back(i);
        for(int j=0;j<(int)primes.size() && i*primes[j]<=MAX;j++){
            isp[i*primes[j]]=false;
            if(i%primes[j]==0) break;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    sieve();
    int n;
    cin>>n;
    ll ans=1;
    for(int p:primes){
        if(p>n) break;
        ll e=0,pw=p;
        while(pw<=n){
            e+=n/pw;
            pw*=p;
        }
        ans=ans*(2*e+1)%MOD;
    }
    cout<<ans<<"\n";
    return 0;
}

樱花

正文

一本通·提高篇的其它内容