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

作者: wjyyy 分类: 分解质因数,同余,数学,筛素数,组合数学,解题报告 发布时间: 2018-09-02 15:54

点击量:23

 

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

 

题目背景

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

题目描述

\(\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;
}

说点什么

avatar
  Subscribe  
提醒
/* */