Factors of Factorial AtCoder - 2286 （N的阶乘的因子个数）（数论）
Problem Statement
You are given an integer <var>N</var>. Find the number of the positive divisors of <var>N!</var>, modulo <var>10^9+7</var>.
Constraints
- <var>1≤N≤10^3</var>
Input
The input is given from Standard Input in the following format:
<var>N</var>
Output
Print the number of the positive divisors of <var>N!</var>, modulo <var>10^9+7</var>.
Sample Input 1
3
Sample Output 1
4
There are four divisors of <var>3!</var> <var>=6</var>: <var>1</var>, <var>2</var>, <var>3</var> and <var>6</var>. Thus, the output should be <var>4</var>.
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';}}}
