Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <cmath>
- #include <cstdio>
- #include <iomanip>
- #include <fstream>
- #include <cassert>
- #include <cstring>
- #include <unordered_set>
- #include <unordered_map>
- #include <numeric>
- #include <ctime>
- #include <bitset>
- #include <complex>
- using namespace std;
- #define cerr if (false) cerr
- #define int unsigned long long
- namespace Miller {
- int p;
- vector<int> need = {2, 3, 5, 7, 11, 17, 21, 27, 29};
- int binmul(int a, int b) {
- int ans = 0;
- while (b) {
- if (b & 1) {
- ans += a;
- ans %= p;
- }
- b >>= 1;
- if (b) {
- a += a;
- a %= p;
- }
- }
- return ans;
- }
- int binpow(int a, int b) {
- int ans = 1;
- while (b) {
- if (b & 1) {
- ans = binmul(ans, a);
- }
- b >>= 1;
- if (b) {
- a = binmul(a, a);
- }
- }
- return ans;
- }
- int tr(int a) {
- int q = p - 1;
- while (q % 2 == 0) {
- q /= 2;
- }
- int cp = q;
- int cur = binpow(a, cp);
- if (cur == 1 || cur == p - 1) {
- return 1;
- }
- while (cp < p - 1) {
- cp *= 2;
- cur = binmul(cur, cur);
- if (cur == p - 1) {
- return 1;
- }
- }
- return 0;
- }
- int solve(int x) {
- if (x == 1) {
- return 0;
- }
- p = x;
- for (auto t : need) {
- if (t == x) {
- return 1;
- }
- if (gcd(t, x) > 1) {
- return 0;
- }
- bool cr = tr(t);
- //cout << t << ' ' << cr << endl;
- if (!cr) {
- return 0;
- }
- }
- //cout << "RETURN 1" << endl;
- return 1;
- }
- } //namespace Miller
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- assert(freopen("again.in", "r", stdin));
- assert(freopen("again.out", "w", stdout));
- int q;
- cin >> q;
- while (q--) {
- int x;
- cin >> x;
- bool tmp = Miller::solve(x);
- if (tmp) {
- cout << "YES" << endl;
- } else {
- cout << "NO" << endl;
- }
- }
- // Miller::p = 1e9 + 239;
- // cout << Miller::binmul(5, 7) << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement