1 条题解

  • 0
    @ 2026-7-20 8:56:01
    /*
    基本的思路
    首先化简可得(x+y)/(x*y)=1/n
    关键一步:令 x=n+a y=n+b
    这一步相当关键,整个题目的精髓所在。
    因为x和y和n都是正整数,要想等式成立,x和y作为分母肯定都要大于n,不然等式成立不了
    代入原公式化简得代入原公式化简得
    n^2=ab
    然后就等价于求解n^2的约数个数了
    */
    
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int mod=1e9+7,N=1e6+5;
    LL n,pr,prime[N];
    bool v[N];
    void get_prime()
    {
        pr=0;memset(v,0,sizeof(v));
        for(LL i=2;i<=n;i++)
        {
            if(v[i]==0) prime[++pr]=i;
    		    
            for(int j=1;(j<=pr)&& (i*prime[j]<=n);j++)
            {
                v[ i * prime[j] ]=1;
                if( i % prime[j] ==0) break;
            }
        }
    }
    int main()
    {
        scanf("%lld",&n);
        get_prime();
        LL ans=1;
        for(LL i=1;i<=pr;i++)
        {
            LL cnt=0;
            for(LL j=prime[i];j<=n;j*=prime[i]) cnt+=n/j;
            cnt%=mod;
            ans=ans*(cnt*2+1)%mod;
        }
        printf("%lld\n",ans);
        return 0;
    }
    
    • 1

    *【线性筛】1/x +1/y =1/n! 的方案数

    信息

    ID
    1763
    时间
    1000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    111
    已通过
    33
    上传者