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

不念不忘少年蓝@ 2024-04-18 08:06 73阅读 0赞

ab =  
       ① ab ，b< p  
       ②ab%∮( p )+∮( p ), b >= p

[题目链接][Link 1]

##### 本题利用知识点： #####

欧拉降幂（指数>= Mod 的情况）  
快速幂  
递归

#include<iostream>
    #include<cstdlib>
    #include<cstdio>
    #define ll long long
    using namespace std;
    ll qpow(ll a, ll n, ll Mod)
    { 
        ll ret = 1;
        while(n)
        { 
            if(n%2)ret = ret*a%Mod;
            a = a*a%Mod;
            n/=2;
        }
    
        return ret;
    }
    ll phi(ll p)
    { 
    
        ll ret = p;
        for( ll i = 2; i*i <= p; i++)
        { 
            if(p %i == 0)
            { 
                ret = ret*(i-1)/i;
                while(p%i == 0)p/=i;
            }
        }
        if(p > 1)ret = ret*(p-1)/p;
        return ret;
    }
    
    ll solve(ll a, ll Mod)
    { 
        if(Mod == 1)return 0;// 剪枝部分 任何数对1取模为 0
    
        if(a == 1)return 1%Mod;/* */
        if(a == 2)return 2%Mod;/* */
        if(a == 3)return 9%Mod;/******/
        if(a == 4)return qpow(4ll, 9ll, Mod);/******因为只是利用欧拉降幂 指数 >= Mod的情况， 根据题意Mod<= 1e9 所以在a == 1~4情况， 降幂公式可能失效******/
    
    
        ll ph = phi(Mod);
        return qpow(a, ph+solve(a-1,ph), Mod);// 利用欧拉降幂指数 大于 >= Mod的情况， 并且根据题意 进行可以进行递归递归
    }
    int main()
    { 
        ll n, p;
        while( cin>>n>>p)
        { 
            cout<< solve(n, p)<<endl;
        }
        return 0;
    }

[Link 1]: https://vjudge.net/problem/Gym-101550E

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

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

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

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

相关 [Gym-101550D] 贪心

道题贪心题，硬生生的让我做成了dp 思路：低价买高价卖找非递减子序列（就是将该段序列看成多个非递减子序列的拼接） include<b...

﹏ヽ暗。殇╰゛Y/ 2024年04月17日 23:44/ 0 赞/ 88 阅读

相关【欧拉函数】CF1731E

[Problem - E - Codeforces][] 题意 ![b42ceb99010c4d24a573e4007dc2736d.png][] 思路对于 k 次操

我会带着你远行/ 2024年02月20日 08:54/ 0 赞/ 23 阅读

相关【思维】Cupcakes Gym - 101243E

Think: 1知识点：思维 2题意：n个学生去吃纸杯蛋糕，每次可以吃\[1, ai\]个，循环队列，一直到将蛋糕吃光，有一个懒惰的家伙，每次吃ai个，如果不足ai个则

分手后的思念是犯贱/ 2022年06月09日 02:13/ 0 赞/ 118 阅读

相关 Gym - 101889E 记忆化搜索

思维还是太将江华，开始一直想dp，就是这一位余数固定时取最小的一个字符串，但是字符串太大，赋值的时候超时，其实根本没必要存字符串，只要记忆化搜索，看看\[pos\]\[res\

青旅半醒/ 2022年05月09日 06:50/ 0 赞/ 140 阅读

相关 gym101915e

include <bits/stdc++.h> define N 10 using namespace std; int a

快来打我*/ 2022年04月24日 11:16/ 0 赞/ 111 阅读

相关欧拉降幂加快速幂

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

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

相关 CF1152E Neko and Flashback——欧拉路径

[RemoteJudge][] 第一次见到欧拉路径的题注意到\\(b\\)和\\(c\\)的构造方法很特殊，即对于一个位置（经过\\(p\\)作用后）\\(i\\)，

Bertha 。/ 2021年12月02日 00:14/ 0 赞/ 221 阅读