首页 > 其他分享 >P1405 苦恼的小明 题解

P1405 苦恼的小明 题解

时间:2023-12-16 15:24:55浏览次数:32  
标签:小明 return 递归 题解 ll varphi P1405 ans define

题目传送门

前置知识

扩展欧拉定理

解法

本题幂塔是有限层的,这里与 luogu P4139 上帝与集合的正确用法 中的无限层幂塔不同,故需要在到达递归边界时进行特殊处理,对于处理 \(varphi(p)\) 在递归过程中等于 \(1\) 的情况两题基本一致。

回忆扩展欧拉定理中的 \(b\) 和 \(\varphi(p)\) 的关系,如果我们按照 常规的快速幂写法 会出现问题,即我们无法正确判断 \(a^b\) 在作为下一次运算的指数时和 \(\varphi(p)\) 之间的大小关系,这就需要我们额外在快速幂的过程中判断 \(a^b\) 和 \(\varphi(p)\) 之间的大小关系。

  • 在这里可以使用 __int128_t 来代替实现高精度的快速幂。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll __int128_t 
#define sort stable_sort 
#define endl '\n'
ll a[1300000];
ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-')
        {
            f=-1;
        }
        c=getchar();
    }
    while('0'<=c&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll phi(ll n)
{
    ll ans=n,i;
    for(i=2;i<=sqrtl(n);i++)//因为使用了__int128_t,为防止CE便使用了sqrtl,亦可以写成i*i<=n的形式
    {
        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 qpow(ll a,ll b,ll p)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=ans*a;
            if(ans>=p)//快速幂特殊处理1
            {
                ans=ans%p+p;
            }
        }
        b>>=1;
        a=a*a;
        if(a>=p)//快速幂特殊处理2
        {
            a=a%p+p;
        }
    }
    return ans;
}
ll f(ll i,ll n,ll p)
{
    return (i==n+1||p==1)?1:qpow(a[i],f(i+1,n,phi(p)),p);//对幂塔进行递归
}
int main()
{
    ll n,i,p=10007;
    n=read(); 
    for(i=1;i<=n;i++)
    {
        a[i]=read();
    }
    printf("%lld\n",f(1,n,p)%p);//因为最后结果小于10007,所以可以放心大胆地当作long long输出
    return 0;
}

标签:小明,return,递归,题解,ll,varphi,P1405,ans,define
From: https://www.cnblogs.com/The-Shadow-Dragon/p/17904868.html

相关文章

  • CF1804F Approximate Diameter 题解
    题目链接点击打开链接题目解法很有意思的题,但不难首先一个显然的结论是:算着边的加入,直径长度递减第一眼看到误差范围是2倍,可以想到二分可以观察到如果取答案为\(\frac{n}{2}\)可以覆盖到\(\frac{n}{4}\)(上下取整不重要),那这样每次可以把值域范围缩小4倍,然后只要二分直......
  • [ARC124C] LCM of GCDs 题解
    题目跳转Fake_Solution前言[warning]:本题解的做法是错法,但是正确概率贼高。离谱的是正确率还可以叠加。正解是记搜,时间复杂度可以证明。正解看文末。思考众所周知一个公式:\[a\timesb=\operatorname{lcm}(a,b)\times\gcd(a,b)\]如果你不知道——自证吧,不难。于是,移一......
  • CF327C Magic Five 题解
    题目传送门前置知识等比数列求和公式|乘法逆元解法设\(lena\)表示\(a\)的长度。首先,若一个数能被\(5\)整除,则该数的末尾一定为\(0\)或\(5\)。故考虑枚举\(a\)中所有的\(0\)和\(5\)的下标,设此下标后面有\(x\)个数字,由于\(s\)是由\(a\)复制\(k\)遍形......
  • gamble 题解报告
    #Galble题解简要题意:  给定一个数$n$AB两人赌博,每次你作为第三者下注任意整数$x$元,A赢则获得$x$元,否则亏损$x$元。任何一个人赢$n$次立刻结束游戏。你需要每次基于现在的情况,计算下的赌注,以使得在整个赌博的全过程,如果A胜利则获得$2^{2n-1}$元,否则亏损这么......
  • 题解 CF1887E【Good Colorings】
    萌萌交互题。对网格图进行二分图建模,左部\(n\)个点表示每一行,右部\(n\)个点表示每一列。若格子\((i,j)\)被染成\(c\)色,就连接\((L_i,R_j,c)\)的边。由抽屉原理易证,在初始局面中至少有一个各边颜色均不同的偶环。获胜条件相当于存在一个各边颜色均不同的四元环。讨论......
  • 洛谷P1824 进击的奶牛 题解 二分答案
    题目链接:https://www.luogu.com.cn/problem/P1824题目大意:本题相当于在\(n\)个数中选\(c\)个数,使得这\(c\)个数中相差最小的两个数之差尽可能地大。解题思路:我们首先可以给\(a_1\sima_n\)从小到大排一下序(这里有点贪心的思想,你会发现很多涉及贪心的问题在排序之后解......
  • ABC332G Not Too Many Balls 题解
    第\(i\)种球有\(a_i\)个,共\(n\)种。第\(i\)种箱子最多共装\(b_i\)个球。共\(m\)种。第\(i\)种球在第\(j\)种箱子里至多放\(ij\)个。问所有箱子放的球数最多是多少。\(1\leqn\leq500,1\leqm\leq5e5,0\leqa_i,b_i\leq1e12\)。很容易建出网络流模型。......
  • CF1784C Monsters (hard version) 题解 线段树
    题目链接:https://codeforces.com/problemset/problem/1784/C题目大意:你面前有\(n\)只怪兽,每只怪兽都有一个初始血量,你可以进行两类操作:操作1:选择任意一个血量大于\(0\)的怪兽,并将它的血量降低\(1\);操作2:将所有存活的怪物的血量各自减去\(1\),如果存在怪物的血量恰好降为......
  • PTA-2023第十三次练习题目题解
    PTA-2023第十三次练习题目题解以下代码已做防抄袭处理,切勿抄袭。注意:手机端因为屏幕限制,代码会有(不希望的)换行。解决方案:1.建议使用电脑端打开。2.点击代码进入全屏观看。6-25实验9_5_反向打印字符串思路就是每次先找到字符串的最后一位,然后输出这一位,输出之后将这一位改为‘......
  • P8818 [CSP-S 2022] 策略游戏 题解
    P8818[CSP-S2022]策略游戏题解题目链接P8818[CSP-S2022]策略游戏简化题意小\(A\)先在\(a[l1,r1]\)中选择一个数\(x\),小\(B\)再在\(b[l2,r2]\)中选择一个数\(y\),最后的分数就是\(x\timesy\)。小\(A\)想让分数尽可能地大,而小\(B\)则想让分数尽可能地小......