fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FR FermatRepresent
  5. namespace FermatRepresent {
  6.     template<class num_t>
  7.     inline num_t mult(num_t a, num_t b, num_t p) {
  8.         num_t q = (num_t) ((long double) a * b / p);
  9.         num_t r = a * b - q * p;
  10.         while (r < 0) r += p;
  11.         while (r >= p) r -= p;
  12.         return r;
  13.     }
  14.     template<class num_t>
  15.     inline num_t fpow(num_t n, num_t k, num_t p) {
  16.         num_t r = 1;
  17.         for (; k; k >>= 1) {
  18.             if (k & 1) r = mult(r, n, p);
  19.             n = mult(n, n, p);
  20.         }
  21.         return r;
  22.     }
  23.     template<class num_t>
  24.     inline num_t isqrt(num_t k) {
  25.         num_t r = sqrt(k) + 1;
  26.         while (r * r > k) r--;
  27.         return r;
  28.     }
  29.     long long func(long long p) {
  30.         srand(2311);
  31.         while (1) {
  32.             long long u = (long long) rand() * rand() % p;
  33.             if (fpow(u, (p - 1) / 2, p) == p - 1) {
  34.                 long long res = fpow(u, (p - 1) / 4, p);
  35.                 return max(res, p - res);
  36.             }
  37.         }
  38.     }
  39.     pair<int, int> calc(long long p) {
  40.         long long a = p, b = func(p);
  41.         long long ip = isqrt(p);
  42.         while (b > ip) {
  43.             a %= b;
  44.             swap(a, b);
  45.         }
  46.         return make_pair(b, isqrt(p - b * b));
  47.     }
  48. }
  49.  
  50. int main() {
  51.     pair<int, int> res = FR::calc(613);
  52.     cerr << res.first << " " << res.second << "\n";
  53.     cerr << res.first * res.first + res.second * res.second << "\n";
  54.     cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  55.     return 0;
  56. }
Success #stdin #stdout #stderr 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
18 17
613

Time elapsed: 2ms
https://ideone.com/y9EcZQ
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!