1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137
| #include <bits/stdc++.h> #define rep(i, l, r) for(int i = (l); i <= (r); i++) #define per(i, r, l) for(int i = (r); i >= (l); i--) #define mem(a, b) memset(a, b, sizeof a)
using namespace std; using ll = long long;
ll mul(ll a, ll b, ll p) { return (a * b - ll((long double)a / p * b + 0.5) * p + p) % p; } ll Pow(ll a, ll n, ll p, ll r = 1) { for(; n; n >>= 1, a = mul(a, a, p)) if(n & 1) r = mul(r, a, p); return r; }
namespace Pollard_Rho { int chk(ll n) { for(ll a : {2, 3, 7, 61, 24251}) { if(n == a) return 1; if(Pow(a, n - 1, n) 1) return 0; ll k = n - 1, t; while(~k & 1) k >>= 1; if((t = Pow(a, k, n)) == 1) continue; while(t != 1 && t != n - 1) t = mul(t, t, n); if(t != n - 1) return 0; } return 1; } ll f(ll x, ll c, ll p) { return (mul(x, x, p) + c) % p; } ll PR(ll n) { ll a = 0, b = 0, c = rand() % (n - 1) + 1, v = 1, g; for(int k = 1; ; k <<= 1, a = b, v = 1) { rep(i, 1, k) { b = f(b, c, n), v = mul(v, abs(a - b), n); if(!(i & 127) || i == k) { g = __gcd(v, n); if(g > 1) return g; } } } } ll ans[100]; int cnt; void solve(ll n) { if(chk(n)) return void(ans[++cnt] = n); ll d; do d = PR(n); while(d == n); solve(d), solve(n / d); } void work() { ll n; while(cin >> n) { cnt = 0; if(chk(n)) { puts("Prime"); continue; } solve(n), sort(ans + 1, ans + cnt + 1); int t = 0; rep(i, 1, cnt) { if(ans[i] != ans[i - 1]) cout << ans[i]; t++; if(ans[i] != ans[i + 1]) { if(t > 1) cout << '^' << t; putchar(32), t = 0; } } putchar(10); } } }; namespace Inv { void exgcd(ll a, ll b, ll& d, ll& x, ll& y) { if(b) exgcd(b, a % b, d, y, x), y -= a / b * x; else d = a, x = 1, y = 0; } void inv(ll a, ll p) { ll d, x, y; exgcd(a, p, d, x, y); if(d > 1) puts("Non-existent!"); else cout << (x % p + p) % p; } void work() { ll a, p; while(cin >> a >> p) inv(a, p); } }; namespace Prime { void work() { ll n; while(cin >> n) { while(!Pollard_Rho::chk(n)) n++; cout << n << endl; } } }; namespace Cipolla { ll n, p, II; struct cmp { ll r, i; cmp operator *(const cmp& b) { return {(r * b.r + i * b.i % p * II) % p, (r * b.i + i * b.r) % p }; } } U = { 1, 0 }; int pow1(ll a, int n, ll r = 1) { for(; n; n >>= 1, a = a * a % p) if(n & 1) r = r * a % p; return r; } cmp pow2(cmp a, int n, cmp r = U) { for(; n; n >>= 1, a = a * a) if(n & 1) r = r * a; return r; } void work() { while(cin >> n >> p) { if(!n) { puts("0"); continue; } if(p == 2) { cout << n << endl; continue; } if(pow1(n, p / 2) != 1) { puts("Non-existent!"); continue; } ll a; do a = rand() % p, II = (a * a - n + p) % p; while(!a || pow1(II, p / 2) == 1); int x1 = pow2({a, 1}, p / 2 + 1).r, x2 = p - x1; if(x1 > x2) swap(x1, x2); printf("%d %d\n", x1, x2); } } }; int main() { srand(time(0)); puts("Press 1 for integer factorization."); puts("Press 2 to calculate the modular multiplicative inverse of a number."); puts("Press 3 to find the first prime number greater than or equal to a number."); puts("Press 4 to calculate the modular square root of a number."); int op; while(1) { cin >> op; if(op == 1) Pollard_Rho::work(); else if(op == 2) Inv::work(); else if(op == 3) Prime::work(); else if(op == 4) Cipolla::work(); else puts("Illegal input! Please re-enter your option."); } }
|