Problem Statement

?

You are given an integer?N. Find the number of the positive divisors of?N!, modulo?10^9+7.

Constraints

?

• 1≤N≤10^3

Input

?

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

N

Output

?

Print the number of the positive divisors of?N!, modulo?10^9+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


題意：　
　　給你一個整數N，求N的結成N！的因子個數，并對1E9+7取模

首先我們應該知道這個的一個性質。
N!=1*2*3*4~~~*n
N!=(2*4*6*8...n)*(1*3*5*7.....*(n-1))
N!=2^(n/2)*(n/2)!*(1*3**5*7*...*(n-1))
所以N規模的問題轉換為N/2規模了，原來求N！含有素數2的個數，等價于求(N/2)!含有素數2的個數加上N/2了。上面是N為偶數的算法，N為奇數時也是一樣。
遞推式f(n, 2) = f(n/2, 2) + n/2，表示n!中2的個數。 同理，推出 f(n, p) = f(n/p, p) + n/p，表示n!中素數p的個數 int f(int n, int p) {if(n==0)return 0;return f(n/p,p) + n/p; }
再介紹下唯一分解定理，
即大于1的任意整數，都可以用質數的次冪的積來表示出來，而且這個表示是唯一的，所以叫唯一分解定理。

這樣我們只需要先處先線性篩把質數都篩出來，然后直接logN來唯一分解出N，


首先來看這樣的一個問題，我們要求N的所有因子個數，我們知道可以sqrt(n)時間復雜度的解決方案，但是顯然太慢了。
我們還有另外一個定理，將N進行唯一分解后，他的所有因子的個數，就是它的質因子的冪次+1的乘積。
例如：
N= p1^t1 * p2^t2 * p3^t3* … * pk^tk（其中，p1, p2, … pk為素數）
那么N的所有因子個數就是num=(t1+1)*(t2+1)*(t3+1)*...*(tk+1)

借助這個定理，我們通過最上面提到的方法把N!唯一分解，
然后就很容易的求出它的所有因子個數。

細節見代碼：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define dll(x) scanf("%I64d",&x) #define xll(x) printf("%I64d\n",x) #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define db(x) cout<<"== [ "<<x<<" ] =="<<endl; using namespace std; typedef long long ll; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll powmod(ll a,ll b,ll MOD){ll ans=1ll;while(b){if(b&1)ans=ans*a%MOD;a=a*a%MOD;b>>=1;}return ans;} inline void getInt(int* p); const int maxn=100010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ bool noprime[maxn]; std::vector<int> p; ll pf[122][3]; int init() {MS0(noprime);p.clear();int m=(int)(sqrt(maxn+0.5));repd(i,2,m){if(!noprime[i]){for(int j=i*i;j<=maxn;j+=i){noprime[j]=1;}}}repd(i,2,maxn){if(!noprime[i]){p.pb(i);}}return p.size(); } int getprifac(ll n,int len) {int pos=0;for(int i=0;p[i]*p[i]<=n&&i<len;i++){if(n%p[i]==0){pf[++pos][0]=p[i];pf[pos][1]=0;while(n%p[i]==0){pf[pos][1]++;n/=p[i];}}}if(n>1){pf[++pos][0]=n;pf[pos][1]=1;}return pos; } ll getnum(ll num,ll x) {if(!num){return 0;}else{return num/x+getnum(num/x,x);} } const ll mod = 1e9+7ll; int main() {// freopen("C:\\Users\\DH_M\\Desktop\\code_io\\in.txt.txt","r",stdin);// freopen("C:\\Users\\DH_M\\Desktop\\code_io\\out.txt.txt","w",stdout); ll n;cin>>n;int len=init();ll ans=1ll;rep(i,0,len){if(p[i]>n)break;ll cnt=getnum(n,p[i]);ans*=(cnt+1ll);ans=(ans+mod)%mod;}cout<<ans<<endl;return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0'); while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}} else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}}}

?

?

轉載于:https://www.cnblogs.com/qieqiemin/p/10547205.html

總結

以上是生活随笔為你收集整理的Factors of Factorial AtCoder - 2286 （N的阶乘的因子个数）（数论）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。