Factors of Factorial(思维公式)

Problem Statement

You are given an integer N. Find the number of the positive divisors of N!, modulo 109+7.

Constraints

• 1≤N≤103

Input

• The input is given from Standard Input in the following format:
• N

Output

• Print the number of the positive divisors of N!, modulo 109+7.

Sample Input 1

3

Sample Output 1

4
There are four divisors of 3! =6: 1, 2, 3 and 6. Thus, the output should be 4.

Sample Input 2

6

Sample Output 2

30

Sample Input 3

1000

Sample Output 3

972926972

解析：分解定理可知，把2~N每个数分解质因数并统计每个质因数出现的个数,然后由公式得出因子个数（a[2]+1）（a[3]+1）(a[4]+1)*……(a[n]+1)，前提是a[i]不为0，为0是没有质因数

#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int maxn=1e9+7;
int a[1005];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));   //a数组赋初值为0
        int c=0;
        for(int i=2; i<=n; i++)
        {
            int l=i;
            for(int j=2; j<=l; j++)
            {
                while(l%j==0)
                {
                    a[j]++;//把每个数de每个素因子的个数存起来
                    l/=j;
                }
            }

        }
        long long sum=1;
        for(int i=2; i<=n; i++)
        {
            if(a[i])
            {
                sum*=(1+a[i]);
                sum=sum%maxn;
            }
        }
        printf("%lld\n",sum%maxn);
    }
    return 0;

}

Thank for you like!

赏

谢谢你de关爱

微信