专栏首页CSDN旧文数学--数论--欧拉降幂--P5091 欧拉定理

数学--数论--欧拉降幂--P5091 欧拉定理

题目背景

出题人也想写有趣的题面,可惜并没有能力。

题目描述

给你三个正整数,a,m,ba,m,ba,m,b,你需要求:ab mod ma^b \bmod mabmodm

输入格式

一行三个整数,a,m,ba,m,ba,m,b

输出格式

一个整数表示答案

输入输出样例

输入 #1 复制

2 7 4

输出 #1 复制

2

输入 #2 复制

998244353 12345 98765472103312450233333333333

输出 #2 复制

5333

说明/提示

注意输入格式,a,m,ba,m,ba,m,b 依次代表的是底数、模数和次数

【样例 111 解释】 24 mod 7=22^4 \bmod 7 = 224mod7=2

【数据范围】 对于 100%100\%100% 的数据,1≤a≤1091\le a \le 10^91≤a≤109,1≤b≤1020000000,1≤m≤1081\le b \le 10^{20000000},1\le m \le 10^81≤b≤1020000000,1≤m≤108。

这个题是模板欧拉降幂

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,m,b;

inline ll read(ll m){
    register ll x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)){
        x=x*10+ch-'0';
        if(x>=m) f=1;
        x%=m;ch=getchar();
    }
    return x+(f==1?m:0);
}

ll phi(ll n){
    ll ans=n,m=sqrt(n);
    for(ll i=2;i<=m;i++){
        if(n%i==0){
            ans=ans/i*(i-1);
            while(n%i==0) n/=i; 
        }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}

ll fast_pow(ll a,ll b,ll p){
    ll ret=1;
    for(;b;b>>=1,a=a*a%p)
        if(b&1) ret=ret*a%p;
    return ret;
}

int main()
{
    scanf("%lld%lld",&a,&m);
    b=read(phi(m));
    printf("%lld\n",fast_pow(a,b,m));
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数学--数论---P4718 Pollard-Rho算法 大数分解

    MillerRabin算法是一种高效的质数判断方法。虽然是一种不确定的质数判断法,但是在选择多种底数的情况下,正确率是可以接受的。PollardRho是一个非常...

    风骨散人Chiam
  • 数学--数论--欧拉降幂和广义欧拉降幂(实用好理解)

    这个代码的优点是,如果b太大,不能读入的话也是可以处理的。 如果代码需要多次计算的话,可以使用线性筛法,获得欧拉函数的值。

    风骨散人Chiam
  • 数学--数论--广义欧拉降幂(模板)

    风骨散人Chiam
  • 扩展欧几里得求乘法逆元

    用户2965768
  • [2019HDU多校第一场][HDU 6582][E. Path]

    题意: t 组样例,n个点,m条边。i 行a到b距离c. 要求去掉最短路的最小代价。去掉每条路代价等于长度。

    用户2965768
  • HDU 6624 (2019杭电第五场 1001) fraction (辗转相除求最小分数解 )

    题意:分数取模的意义是 a/b = x(mod p),告诉你 p和x,求最小的分数解a/b

    用户2965768
  • 2019HDU多校赛第三场 HDU 6608 Fansblog(米勒拉宾判断素数 + 威尔逊定理 )

    威尔逊定理: 即:当且仅当 p为素数时:( p -1 )! ≡ -1 ( mod p )

    用户2965768
  • 51Nod 1004 n^n的末位数字(日常复习快速幂,莫名的有毒,卡mod值)

    1004 n^n的末位数字 题目来源: Author Ignatius.L (Hdu 1061) 基准时间限制:1 秒 空间限制:131072 KB 分值: 5...

    Angel_Kitty
  • Codeforces Round #547 (Div. 3)F1. Same Sum Blocks (Easy)

    This problem is given in two editions, which differ exclusively in the constrain...

    glm233
  • codeforces1216C (矩形面积交)

    给定一块白色矩形和两块黑色矩形和一块白色矩形,询问两块黑色矩形是否能够覆盖到白色矩形

    dejavu1zz

扫码关注云+社区

领取腾讯云代金券