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

蔚落 2021-12-14 07:15 165阅读 0赞

知道降幂公式这题就非常好办了 B>=Phi(c)的时候能够降幂然后高速幂计算，否则就直接高速幂计算。

这里的大数对小数取模直接利用取模性质按位取即可了。

//A^B %C=A^( B%phi(C)+phi(C) ) %C
    #include <cstdlib>
    #include <cstring>
    #include <cstdio>
    #include <iostream>
    #include<string>
    #include<cmath>
    using namespace std;
    typedef __int64 ll;
    int phi(int x)
    {
        int i,j;
        int num = x;
        for(i = 2; i*i <= x; i++)
        {
            if(x % i == 0)
            {
                num = (num/i)*(i-1);
                while(x % i == 0)
                {
                    x = x / i;
                }
            }
        }
        if(x != 1) num = (num/x)*(x-1);
        return num;
    }
    ll quickpow(ll m,ll n,ll k)
    {
        ll ans=1;
        while(n)
        {
            if(n&1) ans=(ans*m)%k;
            n=(n>>1);
            m=(m*m)%k;
        }
        return ans;
    }
    char tb[1000015];
    int main()
    {
        ll a,nb;
        int c;
        while(scanf("%I64d%s%d",&a,tb,&c)!=EOF)
        {
            int PHI=phi(c);
            ll res=0;
            for(int i=0;tb[i];i++)
            {
                res=(res*10+tb[i]-'0');
                if(res>c)break;
            }
            if(res<=PHI)
            {
                printf("%I64d\n",quickpow(a,res,c));
            }
            else
            {
                res=0;
                for(int i=0;tb[i];i++)
                {
                    res=(res*10+tb[i]-'0')%PHI;
                }
                printf("%I64d\n",quickpow(a,res+PHI,c));
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/xfgnongmin/p/10801885.html

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 .mod.c 是什么文件

我们可以为代码清单4.1的模板编写一个简单的Makefile： obj-m := hello.o 并使用如下命令编译Hello World模块： make

深藏阁楼爱情的钟/ 2022年10月01日 03:55/ 0 赞/ 209 阅读

相关 FZU 2122(KMP)

/FZU 2122(简单字符串匹配，KMP算法) 题目大意：就是给你3个字符串，第一个是模式串(用该串在文本串中去查找与之相同的串)即子串，

谁借莪１个温暖的怀抱￠/ 2022年08月10日 14:57/ 0 赞/ 7 阅读

相关 PDSOJ 1759 逃出迷宫

[1759: 逃出迷宫][1759_] 时间限制: 1 Sec 内存限制: 128 MB 提交: 25 解决: 13 \[ [提交][Link 1]\]\

朴灿烈づ我的快乐病毒、/ 2022年06月17日 00:48/ 0 赞/ 115 阅读

相关 FZU-2271——X

Problem 2271 X Accept: 394 Submit: 1635 Time Limit: 1500 mSec Memory Limit : 3

旧城等待，/ 2022年05月19日 00:19/ 0 赞/ 134 阅读

相关 FZU 2273 Triangles

题目：[点击打开链接][Link 1] 题意：判断两个三角形的位置关系。分析：先判断两个三角形的线段是否相交，再判断是否在存在包含关系，剩下的就是相离，相交可以

落日映苍穹つ/ 2022年05月15日 08:36/ 0 赞/ 124 阅读

相关 C++有super关键字么？

很多人在学习Java之后，看到Java里面有super关键字，用来表示父类，那么C++里面有super关键字么？答案是否定的。这也很容易理解，C++由于支持多继承，所以假设

Bertha 。/ 2021年12月22日 06:21/ 0 赞/ 167 阅读

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

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

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

相关 C++ __super关键词用法

首先看微软的Docs上的介绍: Allows you to explicitly state that you are calling a base-class imp

╰半夏微凉°/ 2021年12月03日 15:39/ 0 赞/ 297 阅读

相关 C. Floor and Mod (分块整除)

[题目][Link 1] a/b=i, a%b=i -> a=i\(b+1)，(对于一个b可以配出几个i就可以产生几个贡献)可以知道对于给出的x,y 取任意1<=b<=y

系统管理员/ 2021年07月16日 12:00/ 0 赞/ 372 阅读