---

這題可以使用費馬小定理
long long int pow(long long int x,long long int y)
{
long long int a,c;
if(y==0)
{
return 1;
}
else if(y==1)
{
return x;
}
else
{
a=y/2;
c=y-a;
return pow(x,a)*pow(x,c)%10007;//邊乘編取模
}
}

int main ()
{
long long int x,y,ny;
scanf("%lld",&x);
scanf("%lld",&y);
x=x%10007;
if(x==1||x==0)
{
printf("%lld \n",x);
return 0;
}
y=y%10006;
ny=pow(x,y);
printf("%lld",ny);
}

 

---

如果不會就這樣(費馬小定理應該很少人知道)(包括我,我是問

數學老師才知道的)

 

long long int pow(long long int x,long long int y)

{

long long int a,c;

if(y==0)

{

return 1;

}

else if(y==1)

{

return x;

}

else

{

a=y/2;

c=y-a;

return pow(x,a)*pow(x,c);

}

}

long long int power(long long int x,long long int y,int ny)

{

int nny=0,x1;

x1=x;

x=pow(x,ny)%10007;

nny=y%ny;

y=y/ny;

if(x==1||x==0)

{

if(x==0||x==1)

{

return 1*pow(x1,nny);

} 

}

else

{

for(ny=1;pow(x,ny)<10007;ny++)

{

}

if(x==1||x==0||y<ny)

{

if(x==0||x==1)

{

return 1*pow(x1,nny);

} 

else

{

return pow(x,y)*pow(x1,nny)%10007;

}

}

else

{

return power(x,y,ny)*pow(x1,nny)%10007;

}

}

}

 

 

int main ()

{

   long long int a=1,x,y,ny;

    scanf("%lld",&x);

    scanf("%lld",&y);

    x=x%10007;if(x==1||x==0)

    {

    printf("%lld \n",x);

    return 0;

}

   

for(ny=1;pow(x,ny)<10007;ny++)

{

}

if(y<ny)

{

printf("%d\n",pow(x,y));

}

else{

printf("\n%lld \n",power(x,y,ny));

}

}