欧拉降幂两个模板题

FZU - 1759 Super A^B mod C

Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,C<=1000000000,1<=B<=10^1000000).

Input

There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.

Output

For each testcase, output an integer, denotes the result of A^B mod C.

Sample Input

3 2 4
2 10 1000

Sample Output

1
24

指数太大需要欧拉降幂

亲测用string会T 万能头会CE

暴力求欧拉值就行

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
//const int N=1e5+20;
ll eular(ll n)
{
    ll ans=n;
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans-=ans/i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)
        ans-=ans/n;
    return ans;
}
ll power(ll a,ll b,ll c)
{
    ll ans=1;
    while(b)
    {
        if(b&1==1)
            ans=(ans*a)%c;
        a=(a*a)%c;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll a,c;
    char b[1000050];
    while(~scanf("%lld%s%lld",&a,b,&c))
    {
        ll n=0;
        ll len=strlen(b);
        ll p=eular(c);
//        cout<<p<<'\n';
        for(ll i=0;i<len;i++)
        {
            n=(n*10+b[i]-'0')%p;
        }
        cout<<power(a,n,c)<<'\n';
    }
    return 0;
}

洛谷5091

题目背景

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

题目描述

给你三个正整数，a,m,ba,m,ba,m,b，你需要求：
abmodma^b \bmod mabmodm

输入格式

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

输出格式

一个整数表示答案

输入输出样例

输入 #1复制

2 7 4

输出 #1复制

输入 #2复制

998244353 12345 98765472103312450233333333333

输出 #2复制

说明/提示

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

样例1解释：
24mod7=22^4 \bmod 7 = 224mod7=2
输出2

数据范围：

对于全部数据：
1≤a≤1091≤a≤10^91≤a≤109
1≤b≤10200000001≤b≤10^{20000000}1≤b≤1020000000
1≤m≤1061≤m≤10^61≤m≤106

与上面不同的是这个题需要判断b是否小于eular(m) 如果小于则不需要加上eular(m)

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
ll a,c;
char b[20000500];
//const int N=1e5+20;
ll eular(ll n)
{
    ll ans=n;
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans-=ans/i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)
        ans-=ans/n;
    return ans;
}
ll power(ll a,ll b,ll c)
{
    ll ans=1;
    while(b)
    {
        if(b&1==1)
            ans=(ans*a)%c;
        a=(a*a)%c;
        b>>=1;
    }
    return ans;
}
int main()
{
    while(~scanf("%lld%lld%s",&a,&c,b))
    {
        ll n=0;
        ll len=strlen(b);
        ll p=eular(c);
        int flag=0;
        for(ll i=0;i<len;i++)
        {
            n=n*10+b[i]-'0';
            if(n>=p)
            {
                flag=1;
                n%=p;
            }
        }
        if(flag)
            n+=p;
        cout<<power(a,n,c)<<'\n';
    }
    return 0;
}