Header Ads Widget

Modulo Fermat's Theorem | Hackerearth solution

Rajnish Tripathi 20:00

 Problem

It is well-known that the equation: ��+��=�� has no positive solution for �≥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≤�≤106
  • 1≤�≤1018

 

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 (�,�,�)=(1,1,2).
  • �=2: there is no solution.
  • �=3: this is a solution (�,�,�)=(1,3,2).
  • �=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. }
  34. const int P = 1e6;
  36. int p;
  37. ll L;
  39. int fac[1000], facn;
  40. int rt;
  42. int ocr[P + 9];
  43. bool valid[P + 9];
  45. int pre[P + 9];
  47. int fpm(int a, int b, int mod) {
  48. int ret = 1;
  49. while(b) {
  50. if(b & 1) {
  51. ret = (ll)ret * a % mod;
  52. }
  53. a = (ll)a * a % mod;
  54. b >>= 1;
  55. }
  56. return ret;
  57. }
  59. int gcd(int a, int b) {
  60. return b ? gcd(b, a % b) : a;
  61. }
  63. void findroot() {
  64. for(int i = 2; ; ++i) {
  65. bool fl = true;
  66. for(int j = 2; j <= facn; ++j) {
  67. if(fpm(i, (p - 1) / fac[j], p) == 1) {
  68. fl = false;
  69. break;
  70. }
  71. }
  72. if(fl) {
  73. rt = i;
  74. break;
  75. }
  76. }
  77. }
  79. int main() {
  80. read(p), read(L);
  81. for(int d = 1; d * d < p; ++d) {
  82. if((p - 1) % d == 0) {
  83. fac[++facn] = d;
  84. if(d * d != p - 1) {
  85. fac[++facn] = (p - 1) / d;
  86. }
  87. }
  88. }
  89. findroot();
  90. for(int i = 1; i <= facn; ++i) {
  91. int d = fac[i], base = fpm(rt, d, p);
  92. for(int k = 0, r_k = 1; k < p - 1; k += d, r_k = (ll)r_k * base % p) {
  93. ocr[r_k] = i;
  94. if(ocr[r_k - 1] == i or ocr[r_k + 1] == i) {
  95. valid[d] = true;
  96. break;
  97. }
  98. }
  100. }
  101. for(int i = 1; i < p; ++i) {
  102. pre[i] = pre[i - 1] + valid[gcd(i, p - 1)];
  103. }
  104. ll ans = 0;
  105. ans = L / (p - 1) * pre[p - 1];
  106. ans += pre[L % (p - 1)];
  107. std::cout << ans << std::endl;
  108. return 0;
  109. }

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags: