Header Ads Widget

Modulo Fermat's Theorem | Hackerearth solution

 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

  • 1106
  • 11018

 

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. }
  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() {
  71. read(p), read(L);
  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:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Post a Comment

0 Comments