Submission #20380352

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

long long qpow(long long a,long long k,long long p)
{
    long long re=1;
    while (k)
    {
        if (k&1) re=re*a%p;
        a=a*a%p;
        k>>=1;
    }
    return re;
}

int get_phi(int n)
{
    int re=n;
    for (int i=2;(long long)i*i<=n;i++)
    {
        if (n%i==0)
        {
            re=re/i*(i-1);
            while (n%i==0) n/=i;
        }
    }
    if (n>1) re=re/n*(n-1);
    return re;
}

long long get_pow(long long a,long long b,long long p)
{
    long long phi=get_phi(p);
    if (__gcd(a,p)==1) return qpow(a,b%phi,p);
    if (b<phi) return qpow(a,b,p);
    return qpow(a,b%phi+phi,p);
}

long long solve(long long a,long long b,long long c)
{
    long long phi=get_phi(10);
    if (__gcd(a,10ll)==1)
    {
        long long k=get_pow(b,c,phi);
        return qpow(a,k,10);
    }
    if (b==1) return a%10;
    if (b==2 && c==1) return a*a%10;
    if (b==3 && c==1) return a*a%10*a%10;
    long long k=get_pow(b,c,phi)+phi;
    return qpow(a,k,10);
}

int main()
{
    long long a,b,c;
    cin>>a>>b>>c;
    cout<<solve(a,b,c);
    getchar(); getchar();
    return 0;
}

Submission Info

Judge Result