问题 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;

}