欧拉降幂，基本计算定理——cf615D

男娘i 2023-10-12 08:22 11阅读 0赞

用基本算数定理求约数和的思想来计算，

首先用pi,ci来表示第i个质数，指数为i，然后对于每个pi,pi^2...都有指数为mul\{(c\_1+1)(c\_2+1)(c\_i-1+1)(c\_i+1+1)...\}的贡献，所以枚举累乘即可

注意要用欧拉降幂来计算质数，同时用中间挖掉一个值的累乘，可以预处理前缀后缀乘积来做

/*
    枚举每个不同的质因子pi，枚举其指数[1,ci]
    累乘每个pi^ci的贡献即可 
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define N 200005
    #define ll long long
    #define mod 1000000007
    
    ll n,a[N];
    ll p[N],c[N],m;
    ll suf[N],pre[N],ans;
    ll Pow(ll a,ll b){
        ll res=1;
        while(b){
            if(b%2)
                res=res*a%mod;
            b>>=1;a=a*a%mod;
        }
        return res;
    }
    
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++){
            if(p[m]!=a[i]){
                p[++m]=a[i];
                c[m]=1;
            }    
            else c[m]++;
        } 
        
        suf[m+1]=1;pre[0]=1;
        for(ll i=m;i>=1;i--)
            suf[i]=suf[i+1]*(c[i]+1)%(mod-1);
        for(ll i=1;i<=m;i++)
            pre[i]=pre[i-1]*(c[i]+1)%(mod-1);
        
        ans=1;
        for(ll i=1;i<=m;i++){
            ll tmp=1;
            ll prod=pre[i-1]*suf[i+1]%(mod-1);
            for(ll j=1;j<=c[i];j++){
                tmp=tmp*p[i]%mod;
                ans=ans*Pow(tmp,prod)%mod;
            } 
        }
        cout<<ans<<endl;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11439143.html

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关 FZU-1759——(欧拉降幂，模板题)

题目链接][Link 1] 思路：因为指数非常大，用long long 都存不下，所以要用数组存，然后在通过欧拉降幂取模是指数变小，在通过快速幂求结果注...

港控/mmm°/ 2024年04月18日 09:28/ 0 赞/ 63 阅读

相关数论12——欧拉——欧拉降幂

拉降幂，广义欧拉降幂 ab = ① ab ，b< p ②ab%∮( p )+∮( p ), b >= p 代码（改代码用于解...

╰半夏微凉°/ 2024年04月18日 08:08/ 0 赞/ 65 阅读

相关 E - Exponial Gym - 101550E——(欧拉降幂)

b = ① ab ，b< p ②ab%∮( p )+∮( p ), b >= p [题目链接][Link 1] 本题利用知识点：...

不念不忘少年蓝@/ 2024年04月18日 08:06/ 0 赞/ 64 阅读

相关欧拉降幂，基本计算定理——cf615D

用基本算数定理求约数和的思想来计算，首先用pi,ci来表示第i个质数，指数为i，然后对于每个pi,pi^2...都有指数为mul\{(c\_1+1)(c\_2+1)(c\

男娘i/ 2023年10月12日 08:22/ 0 赞/ 12 阅读

相关 HDU 1395(欧拉定理)

欧拉φ函数的值　通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0

绝地灬酷狼/ 2022年09月20日 12:49/ 0 赞/ 167 阅读

相关 Hdu 3221 Brute-force Algorithm (矩阵欧拉定理降幂)

利用迭代思想，最后推得的规律和Hdu4549一样，我的Hdu4549题解：http://blog.csdn.net/whyorwhnt/article/details/1285

Bertha 。/ 2022年09月17日 12:19/ 0 赞/ 140 阅读

相关欧拉定理费马小定理

欧拉定理： > 若gcd(a,m)=1 g c d ( a , m ) = 1 ，则aφ(m)≡1(modm) a φ ( m ) ≡ 1 ( mod m ) 。其中

本是古典何须时尚/ 2022年06月02日 10:44/ 0 赞/ 193 阅读

相关欧拉降幂加快速幂

题：[https://ac.nowcoder.com/acm/contest/634/D][https_ac.nowcoder.com_acm_contest_634_D]

川长思鸟来/ 2022年04月24日 08:12/ 0 赞/ 158 阅读

相关欧拉定理

费马小定理:如果一个P是素数,并且:gcd(a,p)==1.那么：(a^P)%P==a;//反向利用这个定理可以证明一个数是不是素数（多个a）欧拉定理\{ 欧

野性酷女/ 2022年03月20日 08:24/ 0 赞/ 263 阅读

相关欧拉函数|(扩展)欧拉定理|欧拉反演

[也许更好的阅读体验][Link 1] 欧拉函数欧拉函数是小于 n的数中与n 互质的数的数目符号\\(\\varphi(x)\\)

忘是亡心i/ 2021年11月09日 20:06/ 0 赞/ 432 阅读