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

港控/mmm° 2024-04-18 09:28 79阅读 0赞

[题目链接][Link 1]

##### 思路： #####

因为指数非常大，用long long 都存不下， 所以要用数组存， 然后在通过欧拉降幂取模是指数变小，在通过快速幂求结果

注：这里只用到了欧拉降幂中 指数大于等于模数的情况

#include<iostream>
    #include<cstring>
    #define ll long long
    using namespace std;
    const int maxn = 1000005;
    ll qpow(ll a, ll n, ll mod)
    { 
        ll ret = 1;
        while(n)
        { 
            if(n%2) ret = (ret%mod)*(a%mod)%mod;
            a = (a%mod)*(a%mod)%mod;
            n/=2;
        }
        return ret;
    }
    ll phi(ll x)
    { 
        ll ret = x;
        for(ll i = 2;i*i <= x;i++)
        { 
            if(x%i == 0)
            { 
                ret = ret*(i-1)/i;
                while(x%i == 0)x/=i;
            }
        }
        if(x > 1)ret = ret*(x-1)/x;
        return ret;
    }
    int main()
    { 
        ios_base::sync_with_stdio(false);
        ll a, c;
        char b[maxn];
        while(cin>>a>>b>>c)
        { 
            ll n = 0;
            ll len = strlen(b);
            if(len<= 10)
            { 
                for(int i = 0;i < len;i++)
                { 
                    n = n*10+b[i]-'0';
                }
    
            }
            else // 指数长度大于10 肯定大于模数
            { 
                ll ph = phi(c);
                for(int i = 0;i < len;i++)
                { 
                    n = (n*10+b[i] - '0')%ph;
                }
                n += ph;
            }
            cout<<qpow(a, n, c)<<endl;
        }
    
    
        return 0;
    }

[Link 1]: https://cn.vjudge.net/problem/FZU-1759

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关 [模板] 欧拉回路

欧拉路给定一个无向图, 求一条恰好经过每条边恰好一次的路径. 如果所有点度数均为偶数, 存在欧拉回路; 如果有且仅有两个点度数为奇数, 存在以这两个点为起点, 终点的

客官°小女子只卖身不卖艺/ 2023年08月17日 17:16/ 0 赞/ 196 阅读

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

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

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

相关欧拉函数模板

欧拉函数模板欧拉函数是用来求给定一个属n，小于等于n的与n互质的数的数目代码： include <bits/stdc++.h> using names

向右看齐/ 2022年05月31日 09:44/ 0 赞/ 223 阅读

相关欧拉降幂加快速幂

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

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

相关 FZU - 1759 Super A^B mod C 降幂公式

知道降幂公式这题就非常好办了 B>=Phi(c)的时候能够降幂然后高速幂计算，否则就直接高速幂计算。这里的大数对小数取模直接利用取模性质按位取即可了。 //A^B

蔚落/ 2021年12月14日 07:15/ 0 赞/ 179 阅读

相关吉首大学校赛 A SARS病毒（欧拉降幂）

链接：[https://ac.nowcoder.com/acm/contest/925/A][https_ac.nowcoder.com_acm_contest_925_A]

青旅半醒/ 2021年12月11日 01:03/ 0 赞/ 237 阅读