您的位置:首页 > 娱乐 > 明星 > 搜索域名_网站seo外包技术资源_临沂seo排名外包_郑州网站制作公司

搜索域名_网站seo外包技术资源_临沂seo排名外包_郑州网站制作公司

2024/12/23 8:05:14 来源:https://blog.csdn.net/m0_73669127/article/details/142595710  浏览:    关键词:搜索域名_网站seo外包技术资源_临沂seo排名外包_郑州网站制作公司
搜索域名_网站seo外包技术资源_临沂seo排名外包_郑州网站制作公司

题目


在这里插入图片描述



思路

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

  1. 首先,易知 x , y > n ! x, y > n! x,y>n!
  2. y = n ! + k , k ∈ Z + y=n!+k, \;k \in Z_{+} y=n!+k,kZ+
  3. 代入原方程,得到参数方程组
    { x = n ! + ( n ! ) 2 k y = n ! + k \left\{\begin{matrix} x &=&n!&+& \frac{(n!)^{2}}{k}\\ y&= & n!&+&k \end{matrix}\right. {xy==n!n!++k(n!)2k
  4. 根据单调性, k k k 的个数就是 ( x , y ) (x,y) x,y的个数
  5. 那么这个问题就被转化成了:如何求n!^{2}的约数个数
  • 如何求 x x x 约数个数?
    • x x x 作质因数分解
    • 约数个数 = ∏ i = 1 c n t ( s [ p i ] + 1 ) \prod_{i=1}^{cnt}(s[p_{i}]+1) i=1cnt(s[pi]+1)
    • 注意这里我们先求 n ! n! n! 的质因数分解,每个质因数的指数乘2就行,就是 ( n ! ) 2 (n!)^{2} (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;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com