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

╰半夏微凉° 2024-04-18 08:08 87阅读 0赞

欧拉降幂， 广义欧拉降幂  
ab =  
       ① ab ，b< p  
       ②ab%∮( p )+∮( p ), b >= p

##### 代码（改代码用于解决塔型指数 ——abcd. . .） #####

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 101010
    #define MOD(a,Mod) a>=Mod?a%Mod+Mod:a//a为指数 Mod为模数。 如果指数大于等于模数 返回a%Mod+Mod, 否则返回a（该部分就是欧拉定理的应用）。
    #define ll long long
    unordered_map<int,int>mp;
    int n,q,l,r;
    ll m,w[maxn];
    ll qpow(ll a,ll b,ll mod)
    { 
        ll res=1;
        while(b)
        { 
            if(b&1)res=MOD(res*a,mod);//同余
            a=MOD(a*a,mod);// 同余
            b>>=1;
        }
        return res;
    }
    ll phi(ll k)// 求欧拉函数部分
    { 
        ll x=k,s=k;
        if(mp.count(k))return mp[k];
        for(int i=2; i*i<=k; i++)
        { 
            if(k%i==0)s=1ll*s/i*(i-1);
            while(k%i==0) k/=i;
        }
        if(k>1)s=s/k*(k-1);
        mp[x]=s;
        return s;
    }
    ll solve(int id,ll mod)// 解决部分
    { 
        if(id==r||mod==1)return MOD(w[id],mod);// mod == 1是剪纸部分， id == r 是边界
        return qpow(w[id],solve(id+1,phi(mod)),mod);//递归操作
    }
    int main()
    { 
        scanf("%d%lld",&n,&m);
        for(int i=1; i<=n; i++)scanf("%lld",&w[i]);// W[i] 储存塔型数（从底， 到最后一个指数）
        scanf("%lld",&q);
        while(q--)
        { 
            scanf("%d%d",&l,&r);// l表示底的编号， r表示最后一个指数的编号
            printf("%lld\n",solve(l,m)%m);//结果要取模
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

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

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

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

相关欧拉回路和欧拉道路

即一笔画问题。起点和终点相同称为回路，否则称为道路欧拉回路或道路存在判定无向图联通,有0个或2个奇点(度为奇数)。如果有两个奇点，则必须从一个奇点出发

墨蓝/ 2022年05月09日 05:36/ 0 赞/ 294 阅读

相关欧拉降幂加快速幂

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

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

相关欧拉回路与欧拉道路

欧拉回路与欧拉道路图G的一个[回路][Link 1]，若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路。如果一个图只是形成一个连通所有节点的链，且每一点只走

末蓝、/ 2021年12月23日 14:39/ 0 赞/ 403 阅读

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

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

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

相关欧拉路，欧拉回路

[欧拉路，欧拉回路][Link 1] 转载于:https://www.cnblogs.com/Al-Ca/p/11206978.html [Link 1]: https:

偏执的太偏执、/ 2021年10月26日 11:44/ 0 赞/ 407 阅读

相关数论 - 欧拉函数【普通求法 + 筛法求欧拉函数】

欧拉函数 1.定义对于正整数n,欧拉函数是小于或等于n的正整数中(即1-n中)与n互质的数的数目，记作φ(n) 其中φ(1)=1。 2求n的

向右看齐/ 2021年07月24日 23:53/ 0 赞/ 463 阅读

相关欧拉回路欧拉通路欧拉回路图

[来源][Link 1] 一、定义对于无向图：　　1) 设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路；　　2) 如果欧拉通路是回路（

灰太狼/ 2021年06月24日 15:57/ 0 赞/ 601 阅读