求root(N, k)

// 网上抄来的，来源：http://www.acmerblog.com/jiudu-1085-2256.html

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include<iostream>

using namespace std;
typedef long long INT;

//计算幂取模a^b mod n, O(logb)

int modular_exponent(INT a,INT b,INT n){

 int ret=1;

 for (;b;b>>=1,a=a*a%n)

  if (b&1)

   ret=ret*a%n;

 return ret;

}


int main()

{

 int x, y, k;

 int i;

 int ret;

 

 while(scanf("%d%d%d", &x, &y, &k) == 3)

 {

  ret = modular_exponent(x, y, k-1);

  if(ret == 0)

   ret = k-1;

  printf("%d\n", ret);

 }

 return 0;

}

#include <stdio.h>

int root(int N,int k)
{
    if(N >= k)
    {
        int num = 0;
        while(N != 0)
        {
            num += N%k;
            N /= k;
        }
        return root(num,k);
    }
    else
        return N;
}
void get(int x,int y,int k)  // root(x*y,k) = root(root(x,k)*root(y,k),k)
{
    int tmp = root(x,k);
    int rtn = 1;
    while(y>0)
    {
        if(y%2 == 1)
        {
            rtn = root(rtn*tmp,k);
        }
        tmp = root(tmp*tmp,k);
        y/=2;
    }
    printf("%d\n",rtn);
}
int main()
{
    int x,y,k;
    while(scanf("%d%d%d",&x,&y,&k) != EOF)
    {
        get(x,y,k);
    }
}

#include <stdio.h>
int main(){
    for(long x,y,k,r;~scanf("%ld%ld%ld",&x,&y,&k);){
        for(r=1,k-=1;y;r=(y&1?r*x%k:r),x=x*x%k,y>>=1);
        printf("%ld\n",r?r:k);
    }
    return 0;
}

try:
    while True:
        x,y,k = list(map(int,input().split()))
        result = 1
        while y:
            if y&1:
                result = (result*x)%(k-1)
            x = (x*x)%(k-1)
            y>>=1
        result = result if result else k-1
        print(result)
except Exception:
    pass

http://blog.sina.com.cn/s/blog_8619a25801010wcy.html

#include<stdio.h>
int mod;
long long FastPow(long long a,long long k){
    long long sum=1;
    while(k){
        if(k&1)sum=sum*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return sum;
}
int main(){
	long long x,y;
	while(scanf("%lld%lld%d",&x,&y,&mod)!=EOF){
        mod--;
		long long p=FastPow(x,y);
		printf("%lld\n",p==0?mod:p);
	}
}

//我用两种方法求这个题。它们思想都是快速幂加上递推式。
//下面是迭代
#include<stdio.h>
typedef long long ll;
//迭代求x^y%k
ll N(ll x,ll y,ll k){
    ll ans=1;
    while(y){
        if(y&1)
            ans=(ans*x)%k;    
        x=(x*x)%k;
        y>>=1;
    }
    if(ans)//模不为0返回模
        return ans;
    else//模为0返回k
        return k;
}
int main(){
    ll x,y,k;
    while(scanf("%lld%lld%lld",&x,&y,&k)!=EOF){//循环输入
        printf("%lld",N(x,y,k-1));
    }
    return 0;
}
//下面是递归
#include<iostream>
using namespace std;
long N(long long x,long long y,long long k){
    long long ans=0;
    if(!y)
        return 1;
    else if(y&1)
        return x*N(x,y-1,k)%k;
    else{
        ans=N(x,y/2,k);
        return ans*ans%k;
    }
}
int main(){
    long long x,y,k,ans;
    while(cin>>x>>y>>k){
        ans=N(x,y,k-1);
        if(ans)
            cout<<ans;
        else
            cout<<k-1;
    }
    return 0;
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
		// TODO 自动生成的方法存根
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			long aa = in.nextLong();
			long bb = in.nextLong();
			long kk = in.nextLong();
			//快速幂取模
			long ans = 1;
			kk--;
			while (bb > 0) {
				if (bb%2==1) {
					ans = (ans*aa)%kk;
					
				}
				bb/=2;
				aa=(aa*aa)%kk;
			}
			System.out.println(ans==0?kk:ans);
			
		}
	}

}

#include <iostream>
using namespace std;
int root(long long a,long long b,int mod){
    int answer = 1;
    while(b>0){
        if(b % 2==1)
            answer=answer*a%mod;        
        b/=2;
        a=a*a%mod;
    }
    return answer>0?answer:mod;
}
int main() {  
    long long x,y;
    int k;
    while(cin>>x>>y>>k){
        cout<<root(x,y,k-1)<<endl;
    }
}

#include <iostream>
using namespace std;

long long FastPow(long long a, long long k, const int mod){
    if(k==0)
        return 1;
    if(k%2==1){
        return FastPow(a, k-1, mod) * a % mod;
    } else {
        long long ans = FastPow(a, k/2, mod);
        return ans * ans % mod;
    }
}

int main() {
    int x, y, k;
    while(cin>>x>>y>>k){
        k --;
        long long ans = FastPow(x, y, k);
        if(ans==0)
            cout<<k<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
long long root(long long x,long long y,int k)
{
    long long ans = 1;
    while(y!=0)
    {
        if(y%2==1)
        ans = x*ans%k;
        y/=2;
        x = x*x%k;
    }
        return ans;
}
int main()
{
    int x,y,k;
    cin>>x>>y>>k;
    int ans = root(x,y,k-1);
    if(ans == 0)
        ans = k-1;
    cout<<ans<<endl;
    return 0;
}