NOIp模拟题 堆叠 题解【组合数学】【分解质因数】【同余】

点击量：176

    一道有一定思维难度和代码技巧的数学问题。

目录

题目背景

把朴素的原子们堆叠在一起，才能有分子呀。

题目描述

\(\mathrm{NiroBC}\)是造物主，她创造了\(k\)个质数\(p_1,p_2,p_3,\cdots ,p_k\)​，将这些质数堆叠起来，创造出了一个正整数\(n=p_1p_2p_3\cdots p_k\)。

\(\mathrm{NiroBC}\)是一个无聊的造物主，她想知道\(n\)的所有正约数的积是多少。

输入输出格式

输入格式：

第一行，一个正整数\(k\)。

第二行，\(k\)个质数，分别表示\(p_1,p_2,p_3,\cdots ,p_k\)。

输出格式：

一行一个整数，表示的所有正约数的积对\(1000000007\)取模的结果。

输入输出样例

输入样例#1：

3
2 3 2

输出样例#1：

1728

说明

\(n=12\)，它的正约数有\(1,2,3,4,6,12\)，乘积为\(1\times 2\times 3\times 4\times 6\times 12=1728\)。

对于\(30\%\)的数据，\(k,p_i\le 100\)；

对于\(100\%\)的数据，\(k,p_i\le 200000\),所有\(p_i\)​都是质数，可能有相同的。

题解：

    这个题手玩都很难玩，需要一定的手玩技巧。一开始试了几个答案都找不出来规律。。。

    首先我们要知道一个数\(N=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}\)的约数个数

$$C=\prod_{i=1}^{m}(c_i+1)$$

    如果没有重复元素，我们只需要对每一个元素乘上其他的元素中任选\(0,1,2,\cdots,k-1\)个的方案数，也就是\(2^{k-1}\)，总共的乘积就是\(2^{k-1}\times \prod_{i=1}^ka_i\)，也就是答案。

    但是有重复元素，而且在重复元素里选相同个数时只能计算一次，那么我们就把\(a^p\)看作\(a^1,a^2,\cdots,a^p\)，当作了\(p\)个元素。对于\(a^p\)，每次只能在这\(p\)个元素中选1个，然后把作为\(a^1,a^2,\cdots,a^p\)的答案全部统计一遍相乘。此时直接对其他元素使用约数个数和公式，\(a^p\)的贡献要乘上其他元素的约数个数和次。

    设\(N\)的约数个数和为\(C\)，那么\(C=\prod_{i=1}^{m}(c_i+1)\)。统计剩下的约数个数，就要用原来的约数个数和除以当前元素贡献的约数个数即\(c_i+1\)。而因为上述贡献是乘起来的，也就是\(a^1\dot a^2\dot \cdots a^p\)，所以在答案中指数要相加，就是\(\frac {p(p+1)}2\)。

注意公式中\(C\)的大小写

    因此对于元素\(i\)，设\(a_i\)出现次数为\(c_i\)(即前两段推的\(p\))，那么答案为\(ans_i=a_i^{\frac C{c_i+1}\times \frac {c_i(c_i+1)}2}\)。最终答案为\((\prod\limits_{i=1}^k ans_i)\mod 1,000,000,007\)。

    可以看出，指数可能很大，这时我们就要把它\(\mod \varphi (1,000,000,007)=1,000,000,006\)。但是发现指数上要除以\(2\)(\(c_i+1\)可以约掉)，我们发现\(2^{-1}(\mod 1,000,000,006)\)不存在，可以选择使用高端的CRT合并，也可以用下面的方法。

    在约分后，每一种元素的答案是\(ans_i=a_i^{\frac {C\times c_i}2\mod 1,000,000,006}\)，我们要处理这个2。我们知道\(C=\prod_{i=1}^k(c_j+1)\)，那么\(i\in j\)，所以\((c_i+1)|C\)。那么\((c_i+1)\cdot c_i|C\cdot c_i\)，我们又知道\((c_i+1)\cdot c_i\)一定是个偶数，因此这个2是可以在处理\(C\)的时候就除掉的。所以在算指数的时候只处理一个，剩下的直接乘起来mod 1,000,000,006就可以了。注意非指数部分还是要mod 1,000,000,007。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
long long C=1;
int a[210000];
int cnt[210000];

long long qpow(long long x,long long y)
{
    long long ans=1,m=x;
    while(y)
    {
        if(y&1)
            ans*=m;
        ans%=1000000007;
        m*=m;
        m%=1000000007;
        y>>=1;
    }
    return ans;
}
long long ans=1;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    std::sort(a+1,a+1+n);
    for(int i=1;i<=n;++i)//统计每个元素出现的次数
    {
        if(a[i]!=a[i-1])
            ++a[0];
        ++cnt[a[0]];
    }
    std::unique(a+1,a+1+n);
    int flag=0;
    for(int i=1;i<=n;++i)
    {
        if(!flag&&!((cnt[i]+1)&1))//为偶数
        {
            flag=1;
            C*=((cnt[i]+1)>>1);
        }
        else
            C*=cnt[i]+1;
        C%=1000000006;
    }
    for(int i=1;i<=a[0];++i)
        if(!flag)//在大C中没有发现偶数，这里就一定是偶数
            cnt[i]>>=1;
    for(int i=1;i<=a[0];++i)
    {
        ans*=qpow(a[i],C*cnt[i]%1000000006);
        ans%=1000000007;
    }
    printf("%lld\n",ans);
    return 0;
}