• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Mar 24th, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <math.h>
3. #include <vector>
4. #include <random>
5. #include <chrono>
6. #include <fstream>
7.
8. using namespace std;
9.
10. uint64_t powmod(uint64_t base, uint64_t exp, uint64_t modulo)
11. {
12.     unsigned res = 1;
13.
14.     while (exp != 0)
15.     {
16.         if ((exp & 1) != 0)
17.         {
18.             res = (1ll * res * base) % modulo;
19.         }
20.
21.         base = (1ll * base * base) % modulo;
22.         exp >>= 1;
23.     }
24.
25.     return res;
26. }
27.
28. vector<uint64_t> factorize(uint64_t base) {
29.     vector<uint64_t> result;
30.
31.     uint64_t possible_divider = 2;
32.
33.     while(base > 1) {
34.         if (base % possible_divider == 0) {
35.             base = base / possible_divider;
36.             result.push_back(possible_divider);
37.         }
38.         else {
39.             ++possible_divider;
40.         }
41.     }
42.
43.     return result;
44. }
45.
46. int main() {
47.     fstream input("primes.in", ios::in);
48.     fstream output("roots.out", ios::out);
49.
50.     uint64_t num;
51.     input >> num;
52.     std::mt19937 gen(static_cast<unsigned>(time(nullptr)));
53.
54.     for (int i = 0; i < num; ++i) {
55.         uint64_t prime_in;
56.         input >> prime_in;
57.         uint64_t minus_1 = prime_in - 1;
58.         vector<uint64_t> dividers = factorize(minus_1);
59.         bool root_not_found = true;
60.         int root = -1;
61.
62.         for(int j = 0; j < 1000 && root_not_found; ++j) {
63.             uint64_t r = gen() % (prime_in - 3) + 2;
64.             uint64_t prev_divider = 0;
65.             bool is_root = true;
66.
67.             for(int k = 0; k < dividers.size() && is_root; ++k) {
68.                 if (dividers[k] != prev_divider) {
69.                     // do smth
70.                     uint64_t power = minus_1 / dividers[k];
71.                     uint64_t r_pow = powmod(r, power, prime_in);
72.                     prev_divider = dividers[k];
73.
74.                     if (r_pow == 1) {
75.                         is_root = false;
76.                     }
77.                 }
78.             }
79.
80.             if (is_root) {
81.                 root_not_found = false;
82.                 root = r;
83.             }
84.         }
85.
86.         output << root << "\n";
87.     }
88.
89.     input.close();
90.     output.close();
91.
92.     return 0;
93. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top