#include <iostream.h>
void main()
{ 
	int c;
	int l,m,n;
	int x,r,p;
	int cc[10000];
	cout<<"x=";
	cin>>x;
	cout<<"r=";
	cin>>r;
	cout<<"p=";
	cin>>p;
	l=r;
	c=1;
	n=0;
  /*---------將指數(shù)轉(zhuǎn)換為2進(jìn)制數(shù)-------*/
    while(l!=0)
		{
			m=l%2;
			if(m==0)
			{
				cc[n]=0;
				n++;
			}
			else
			{
				cc[n]=1;
				n++;
			}
            l=l/2;
		}
  /*-------快速指數(shù)模算法-------*/
	 n=n-1;
     while(n>=0)
     {
         c=(c*c)%p;
		 if(c>(p-1)/2)
		 {
			 c=p-c;
		 }
         if(cc[n]==1)
         {
             c=(c*x)%p;
         }
       n--;
     }
     cout<<endl;       
     cout<<"x"<<"的"<<"r"<<"次方模"<<"p"<<"的結(jié)果是"<<c<<endl;
}