fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zIJAsc
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!