fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long int N=1000010;
  4. long long t,a,n,p,hold,phi[N];
  5. int temp[N];
  6. long long power(long long a,long long b)
  7. {
  8. long long res=1;
  9. while(b)
  10. {
  11. if(b&1)
  12. {
  13. res=(res*1LL*a)%p;
  14. }
  15. a=(a*a)%p;
  16. b>>=1;
  17. }
  18. return res;
  19. }
  20. void sieve()
  21. {
  22. phi[1]=1;
  23. for(long long int i=2;i<N;i++)
  24. {
  25. if(phi[i]!=0)continue;
  26. phi[i]=i-1;
  27. for(long long j=2*i;j<N;j+=i)
  28. {
  29. if(!phi[j])
  30. phi[j]=j;
  31. phi[j]=phi[j]/i*(i-1);
  32. }
  33. }
  34. }
  35. int main(int argc, char const *argv[])
  36. {
  37. scanf("%lld",&t);
  38. sieve();
  39. for(int tt=1;tt<=t;tt++)
  40. {
  41. scanf("%lld%lld%lld",&a,&n,&p);
  42. memset(temp,-1,sizeof(temp));
  43. if(__gcd(a,p)==1)
  44. {
  45. hold=1;
  46. for(int i=1;i<=n;i++)
  47. {
  48. hold=(hold*i)%(phi[p]);
  49. }
  50. cout<<"Case #"<<tt<<": "<<power((long long)a,hold)%p<<"\n";
  51. }
  52. else
  53. {
  54. temp[1]=0;
  55. int x,c;
  56. long long mul=1;
  57. for(int i=1;;i++)
  58. {
  59. if(temp[mul*a%p]!=-1)
  60. {
  61. x=temp[mul*a%p];
  62. c=temp[mul]+1-x;
  63. break;
  64. }
  65. else
  66. {
  67. temp[mul*a%p]=temp[mul]+1;
  68. mul=mul*a%p;
  69. }
  70. }
  71. hold=1;
  72. //cout<<"x= "<<x<<" c= "<<c<<endl;
  73. for(int i=1;i<=n;i++)
  74. {
  75. hold=(hold*i)%(c);
  76. }
  77. hold=(hold-x+c)%c;
  78. while(hold<0)
  79. hold+=c;
  80. hold%=c;
  81. cout<<"Case #"<<tt<<": "<<(power((long long)a,hold)%p*power(a,x)%p)%p<<"\n";
  82. }
  83. }
  84. return 0;
  85. }
Success #stdin #stdout 0.04s 27784KB
stdin
Standard input is empty
stdout
Standard output is empty