问题 E: 樱花
问题 E: 樱花
时间限制: 1 Sec 内存限制: 128 MB
提交: 27 解决: 9
[提交][状态][讨论版][命题人:150112200121][Edit] [TestData]
题目链接：http://acm.ocrosoft.com/problem.php?cid=1701&pid=4
题目描述
求不定方程：
1/x+1/y=1/n!
的正整数解 (x,y)(x,y)(x,y) 的数目。
输入
一个整数 n。
对于 30% 的数据，n≤100；
对于全部数据，1≤n≤106。
输出
一个整数，表示有多少对 (x,y) 满足题意。答案对 109+7 取模。
样例输入
2 样例输出
3 思路：将x设为=n!+a,y=n!+b可以将原式化为a*b=(n!)*(n!)，相当于在算(n!)*(n!)有几个因数，然后排列组合推出，因数个数和为（c1+1）*(c2+1)......ck为质因数分解后各个质数的幂指数，具体见代码。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define maxn 1000005
#define INF 0x3f3f3f3f
int v[maxn], prime[maxn][2];
int m = 0;
void xianxing(int n)//线性筛
{
for (int i = 2; i <= n; i++)
{
if (v[i] == 0)
{
v[i] = i;
prime[++m][0] = i;
}
for (int j = 1; j <= m; j++)
{
if (prime[j][0] > v[i] || prime[j][0] * i > n)
{
break;
}
v[i*prime[j][0]] = prime[j][0];
}
}
/*for (int i = 1; i <= m; i++)
{
cout << prime[i] << " ";
}*/
}
int main()
{
//将x设为=n!+a,y=n!+b可以将原式化为a*b=(n!)*(n!)，相当于在算(n!)*(n!)有几个因数
xianxing(1000000);//线性筛
int n;
cin >> n;
int sum = 0;
for (int i = 1; i <= m; i++)//利用n!中p（p为质数）的个数为 求和n/（p的k次方） ，k为1到正无穷，将n！质因数分解
{
if (prime[i][0] > n)break;//质数都比输入的大了，没必要去判断了，直接break
for (int j = 1; j <= 1000000; j++)
{
if (pow(prime[i][0], j) > n)break;//后面全为0，加了也没意义，直接break
//cout<<pow(prime[i][0],j)<<endl;
prime[i][1] += int(n / pow(prime[i][0], j));
//cout<<prime[i][1]<<" ";
//cout<<int(n/pow(prime[i][0],j))<<" ";
}
sum++;
//cout<<endl;
}
//cout<<sum<<endl;
/*
for(int i=1;i<=sum;i++)
{
cout<<prime[i][1]<<endl;
}*/
for (int i = 1; i <= sum; i++)
{
prime[i][1] *= 2;//(n!)*(n!)的各个因数的个数刚好是n!各个个数的两倍
}
ll result = 1;
//排列组合推出，因数个数和为（c1+1）*(c2+1)......ck为质因数分解后各个质数的幂指数
for (int i = 1; i <= sum; i++)
{
result = ((result%mod)*(prime[i][1] + 1) % mod) % mod;
}
cout << result << endl;
}
