# Modulo Fermat's Theorem | Hackerearth solution

Problem

It is well-known that the equation: ${�}^{�}+{�}^{�}={�}^{�}$ has no positive solution for $�\ge 3$. But what if we consider solution over a finite field. Now, the task you are given is related to that:

Given a prime $�$, you are asked to count the number of positive integers $�$ doesn't exceed $�$ s.t. modulo equation  has solution $0<�,�,�<�$.

Input Format

A line contains two space-separated integers $�,�$ as described above.

Output Format

Output answer in a single line.

Constraints

• $1\le �\le {10}^{6}$
• $1\le �\le {10}^{18}$

Sample Input
5 4

Sample Output
2

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Let's enumerate all possible values of $�$:

• $�=1:$ there is a solution $\left(�,�,�\right)=\left(1,1,2\right)$.
• $�=2:$ there is no solution.
• $�=3:$ this is a solution $\left(�,�,�\right)=\left(1,3,2\right)$.
• $�=4:$ there is no solution.

So, answer is $2$.

Code(C++):-

1. #include <bits/stdc++.h>
2. #define ll long long
3. #define pii std::pair<int,int>
4. #define mp std::make_pair
5. #define fi first
6. #define se second
7. #define SZ(x) (int)(x).size()
8. #define pb push_back
9. template<class T>inline void chkmax(T &x, const T &y) {if(x < y) x = y;}
10. template<class T>inline void chkmin(T &x, const T &y) {if(x > y) x = y;}
11. template<class T>
12. inline void read(T &x) {
13. char c;int f = 1;x = 0;
14. while(((c=getchar()) < '0' || c > '9') && c != '-');
15. if(c == '-') f = -1;else x = c-'0';
16. while((c=getchar()) >= '0' && c <= '9') x = x*10+c-'0';
17. x *= f;
18. }
19. static int outn;
20. static char out[(int)2e7];
21. template<class T>
22. inline void write(T x) {
23. if(x < 0) out[outn++] = '-', x = -x;
24. if(x) {
25. static int tmpn;
26. static char tmp[20];
27. tmpn = 0;
28. while(x) tmp[tmpn++] = x%10+'0', x /= 10;
29. while(tmpn) out[outn++] = tmp[--tmpn];
30. }
31. else out[outn++] = '0';
32. }
33. const int P = 1e6;
34. int p;
35. ll L;
36. int fac[1000], facn;
37. int rt;
38. int ocr[P + 9];
39. bool valid[P + 9];
40. int pre[P + 9];
41. int fpm(int a, int b, int mod) {
42. int ret = 1;
43. while(b) {
44. if(b & 1) {
45. ret = (ll)ret * a % mod;
46. }
47. a = (ll)a * a % mod;
48. b >>= 1;
49. }
50. return ret;
51. }
52. int gcd(int a, int b) {
53. return b ? gcd(b, a % b) : a;
54. }
55. void findroot() {
56. for(int i = 2; ; ++i) {
57. bool fl = true;
58. for(int j = 2; j <= facn; ++j) {
59. if(fpm(i, (p - 1) / fac[j], p) == 1) {
60. fl = false;
61. break;
62. }
63. }
64. if(fl) {
65. rt = i;
66. break;
67. }
68. }
69. }
70. int main() {
72. for(int d = 1; d * d < p; ++d) {
73. if((p - 1) % d == 0) {
74. fac[++facn] = d;
75. if(d * d != p - 1) {
76. fac[++facn] = (p - 1) / d;
77. }
78. }
79. }
80. findroot();
81. for(int i = 1; i <= facn; ++i) {
82. int d = fac[i], base = fpm(rt, d, p);
83. for(int k = 0, r_k = 1; k < p - 1; k += d, r_k = (ll)r_k * base % p) {
84. ocr[r_k] = i;
85. if(ocr[r_k - 1] == i or ocr[r_k + 1] == i) {
86. valid[d] = true;
87. break;
88. }
89. }
90. }
91. for(int i = 1; i < p; ++i) {
92. pre[i] = pre[i - 1] + valid[gcd(i, p - 1)];
93. }
94. ll ans = 0;
95. ans = L / (p - 1) * pre[p - 1];
96. ans += pre[L % (p - 1)];
97. std::cout << ans << std::endl;
98. return 0;
99. }

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-