题解 P1445 【[Violet]樱花】

2018-04-25 20:33:01


有没有感觉楼下的题解跑的不够快......

所以有没有什么快一点的呢?

那个4ms的12多k的是我的,然后目前除了在13年的记录之外Rnk1.

于是我们分析算法:

楼下题解的复杂度是O(nlogn+常数的),平均200ms

有没有什么更快的呢?

我们分析到了

A*B=(n!)*(n!)

的时候发现最终求的就是约数个数

首先如果求m的约数个数的话,那么对m分解得到

m=p1^k1*p2^k2...

其中p1,p2,p3...都是质数

那么根据乘法原理

Ans = (k1 + 1) * (k2 + 1)...

然后对于阶乘来说,对n!做质因数分解实则在分解1 2 ... * n

然而这个就是楼下的做法,然而由于你实则是需要求质因数的指数,而在《初等数论》中有

公式1

所以我们直接递归(或者非递归地)跑这个公式即可

实际食用:枚举质数(或打表)(在阶乘下质因数等价于质数)(O(n)),然后对于所有质数,跑公式。

n内大约有n/ln(n)个质数,然后每次做都是log的,所以复杂度为O(n/ln(n) * log(n))=O(n),常数小,瓶颈在筛质数那......

代码如下(12kb不忍直视不敢放):

//Source Code

const int MAXN = 1000111;
const int MODS = 1000000007;

int n, tot;
int prime[MAXN];
bool is_not_prime[MAXN];

inline void Get_Prime(){
    for(int i = 2; i <= n; i++){
        if(!is_not_prime[i])
            prime[++tot] = i;
        for(int j = 1; j <= tot; j++){
            if(i * prime[j] > n) break;
            is_not_prime[i * prime[j]] = true;
            if(!(i % prime[j])) break;
        }
    }
}

inline int Get_D(const int &tar, const int &p){
    if(tar < p) return 0;
    return tar / p + Get_D(tar / p, p);
}

int main(){
    Main_Init();
    n = read();
    Get_Prime();
    long long ans = 1;
    for(int i = 1; i <= tot; i++)
        (ans *= (Get_D(n, prime[i]) << 1) + 1) %= MODS;
    write('\n', ans);
    Main_Init();
    return 0;
}