首页 > 其他分享 >SP21690 POWERUP - Power the Power Up 题解

SP21690 POWERUP - Power the Power Up 题解

时间:2023-12-16 19:11:44浏览次数:32  
标签:POWERUP return Power 题解 ll flag ans define

题目传送门

前置知识

扩展欧拉定理

解法

直接对 \(a\) 和 \(b^c\) 分讨,跑一遍扩展欧拉定理就行了。

另外由于本题的特殊规定 \(0^0=1\),故需要在当 \(a=0\) 时,对 \(b^c\) 进行判断。手模几组样例,发现结论挺显然的。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define sort stable_sort 
#define endl '\n'
ll phi(ll n)
{
    ll ans=n,i;
    for(i=2;i<=sqrtl(n);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 qpow(ll a,ll b,ll p,ll phii,ll pd)
{
    ll ans=1,flag=0;
    while(b)
    {
        if(b&1)
        {
            ans=ans*a;
            if(ans>=p)
            {
                flag=1;
                ans%=p;
            }
        }
        b>>=1;
        a=a*a%p;
    }
    return ans+pd*flag*phii;
}
ll gcd(ll a,ll b)
{
    return b?a:gcd(b,a%b);
}
int main()
{
    ll a,b,c,p=1000000007,phii=phi(p);
    while(cin>>a>>b>>c)
    {
        if(a==-1&&b==-1&&c==-1)
        {
            break;
        }
        else
        {
            if(a==0)
            {
                if(b==0&&c!=0)
                {
                    cout<<1<<endl;
                }
                else
                {
                    cout<<0<<endl;
                }
            }
            else
            {
                cout<<qpow(a,qpow(b,c,phii,phii,!(gcd(a,p)==1)),p,phii,0)<<endl;
            }
        }
    }
    return 0;
}

标签:POWERUP,return,Power,题解,ll,flag,ans,define
From: https://www.cnblogs.com/The-Shadow-Dragon/p/17905191.html

相关文章

  • SP10050 POWTOW - Power Tower City 题解
    题目传送门前置知识扩展欧拉定理解法本题幂塔是有限层的,这里与luoguP4139上帝与集合的正确用法中的无限层幂塔不同,故需要在到达递归边界\(n+1\)时进行特殊处理,对于处理\(\varphi(p)\)在递归过程中等于\(1\)的情况两题基本一致。回忆扩展欧拉定理中的\(b\)和\(\v......
  • P1405 苦恼的小明 题解
    题目传送门前置知识扩展欧拉定理解法本题幂塔是有限层的,这里与luoguP4139上帝与集合的正确用法中的无限层幂塔不同,故需要在到达递归边界时进行特殊处理,对于处理\(varphi(p)\)在递归过程中等于\(1\)的情况两题基本一致。回忆扩展欧拉定理中的\(b\)和\(\varphi(p)\)......
  • 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\)遍形......
  • PowerShell配置文件只Profile.ps1
    PowerShell执行的时候,首先会执行Profile.ps1的内容,如果我们想要执行PowerShell的时候,会获得某些功能,可以将想要的内容放到Profile.ps1中。这个文件默认存放在C:\Windows\system32\WindowsPowerShell\v1.0\Examples\下。该文件默认添加所有的别名,还有部分Function。内容如下:#Copyr......
  • gamble 题解报告
    #Galble题解简要题意:  给定一个数$n$AB两人赌博,每次你作为第三者下注任意整数$x$元,A赢则获得$x$元,否则亏损$x$元。任何一个人赢$n$次立刻结束游戏。你需要每次基于现在的情况,计算下的赌注,以使得在整个赌博的全过程,如果A胜利则获得$2^{2n-1}$元,否则亏损这么......
  • Power BI 安全和数据访问权限管理
    介绍PowerBI是微软提供的一款在线软件服务(也称作SaaS,即软件即服务)。通过它,用户能够便捷迅速地制作自助商业智能仪表板、报告、语义模型和可视化效果。使用PowerBI,用户可以连接到众多不同的数据源,整合和处理这些数据源的数据,随后创建可以与他人分享的报告和仪表板。背景随着越......
  • 【Power Shell】启动时自动配置http代理
    背景有时候我们经常需要在WindowsTerminal,powershell内使用http代理来拉去GitHub代码、软件包等等,每次都需要手动配置很麻烦。其实我们可以使用.ps1脚本来启动。https://learn.microsoft.com/zh-cn/powershell/module/microsoft.powershell.core/about/about_scripts?view=pow......
  • 题解 CF1887E【Good Colorings】
    萌萌交互题。对网格图进行二分图建模,左部\(n\)个点表示每一行,右部\(n\)个点表示每一列。若格子\((i,j)\)被染成\(c\)色,就连接\((L_i,R_j,c)\)的边。由抽屉原理易证,在初始局面中至少有一个各边颜色均不同的偶环。获胜条件相当于存在一个各边颜色均不同的四元环。讨论......