【樱花——公式推导，约数个数】

题目

---

思路

条件是一个等式，那么我们可以用一个变量k来表示x,y两个变量

1. 首先，易知 $x,y>n!$
2. 令 $y=n!+k,k\in Z_{+}$
3. 代入原方程，得到参数方程组
   $$\{\begin{array}{ccccc}x& =& n!& +& \frac{(n!{)}^2}{k}\\ y& =& n!& +& k\end{array}$$
4. 根据单调性，$k$ 的个数就是$（x,y）$的个数
5. 那么这个问题就被转化成了：如何求n!^{2}的约数个数

• 如何求 $x$ 约数个数？
  • 对 $x$ 作质因数分解
  • 约数个数 = ${\prod }_{i=1}^{cnt}(s[p_i+1])$
  • 注意这里我们求 $n!$ 的质因数分解，每个质因数的指数乘2就行

---

代码

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long LL;
typedef pair<int, int> PII;

vector<PII> ps;
const int mod = 1e9+7; 
const int N = 1e6+10;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[++cnt] = i;
        for(int j = 1; primes[j] * i <= n; j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
int main()
{
    int n;
    cin >> n;
    get_primes(n);
    for(int i = 1; i <= cnt; i++)
    {
        int p = primes[i];
        LL s = 0;
        int t = n;
        while(t)
        {
            s = s + t / p;
            t /= p;
        }
        ps.push_back({p, 2*s});
    }
    
    LL ans = 1;
    for(auto c : ps)
    {
        int p = c.x, s = c.y;
        ans = (ans * (s+1)) % mod;
    }
    cout << ans % mod;
    return 0;
}

原文地址：https://blog.csdn.net/m0_73669127/article/details/142595710

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！