結果
問題 | No.2954 Calculation of Exponentiation |
ユーザー |
![]() |
提出日時 | 2024-11-08 23:49:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 7,616 bytes |
コンパイル時間 | 3,568 ms |
コンパイル使用メモリ | 262,664 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 23:49:34 |
合計ジャッジ時間 | 4,592 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>#define For(i, a, b) for(int i = a; i < b; i++)#define rep(i, n) For(i, 0, n)#define rFor(i, a, b) for(int i = a; i >= b; i--)#define ALL(v) (v).begin(), (v).end()#define rALL(v) (v).rbegin(), (v).rend()using namespace std;using lint = long long;using ld = long double;int INF = 2000000000;lint LINF = 1000000000000000000;struct Fraction {using lint = long long;private:lint gcd(lint x, lint y) {if (y == 0) {return x;}return gcd(y, x % y);}void reduce() {if (p != 0) {lint g = gcd(abs(p), abs(q));p /= g;q /= g;} else {q = 1;}}int comp(lint a, lint b, lint c, lint d) const {if (a == c && b == d) {return 0;}return (a * d < c * b ? -1 : 1);}public:lint p, q;Fraction() : p(0), q(1) {}Fraction(lint p_, lint q_) : p(p_), q(q_) {assert(q_ != 0);if (q < 0) {p = -p;q = -q;}reduce();}Fraction(lint p_) : p(p_), q(1) {}Fraction &operator+=(const Fraction &a) {lint np = p * a.q + q * a.p;lint nq = q * a.q;*this = Fraction(np, nq);return *this;}Fraction &operator-=(const Fraction &a) {lint np = p * a.q - q * a.p;lint nq = q * a.q;*this = Fraction(np, nq);return *this;}Fraction &operator*=(const Fraction &a) {lint np = p * a.p;lint nq = q * a.q;*this = Fraction(np, nq);return *this;}Fraction &operator/=(const Fraction &a) {assert(a.p != 0);lint np = p * a.q;lint nq = q * a.p;*this = Fraction(np, nq);return *this;}Fraction operator+(const Fraction &a) {return Fraction(*this) += a;}Fraction operator-(const Fraction &a) {return Fraction(*this) -= a;}Fraction operator*(const Fraction &a) {return Fraction(*this) *= a;}Fraction operator/(const Fraction &a) {return Fraction(*this) /= a;}Fraction operator-() {p = -p;return *this;}bool operator==(const Fraction &a) const {return comp(p, q, a.p, a.q) == 0;}bool operator!=(const Fraction &a) const {return comp(p, q, a.p, a.q) != 0;}bool operator<(const Fraction &a) const {return comp(p, q, a.p, a.q) == -1;}bool operator>(const Fraction &a) const {return comp(p, q, a.p, a.q) == 1;}bool operator<=(const Fraction &a) const {return comp(p, q, a.p, a.q) <= 0;}bool operator>=(const Fraction &a) const {return comp(p, q, a.p, a.q) >= 0;}friend ostream &operator<<(ostream &os, Fraction a) {return os << a.p << "/" << a.q;}};namespace fastprime {template <class T>T modpow(T a, T b, T mod) {T cur = a % mod, res = 1 % mod;while (b) {if (b & 1) {res = (res * cur) % mod;}cur = (cur * cur) % mod;b >>= 1;}return res;}bool MillerRabin(long long n) {if (n <= 1) {return false;}if (n == 2 || n == 7 || n == 61) {return true;}if (n % 2 == 0) {return false;}vector<long long> A;if (n < 4759123141) {A = {2, 7, 61};} else {A = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};}long long s = 0, d = n - 1;while (d % 2 == 0) {s++;d >>= 1;}for (auto a : A) {if (a % n == 0) {return true;}long long x = modpow<__int128_t>(a, d, n);if (x == 1) {continue;}bool ok = false;for (int i = 0; i < s; i++) {if (x == n - 1) {ok = true;break;}x = (__int128_t)x * x % n;}if (!ok) {return false;}}return true;}long long gcd(long long x, long long y) {if (y == 0) {return x;}return gcd(y, x % y);}unsigned int xorshift() {static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;unsigned int t = (x ^ (x << 11));x = y;y = z;z = w;return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));}long long Pollard(long long n) {if (n % 2 == 0) {return 2LL;}if (MillerRabin(n)) {return n;}long long i = 0;while (true) {i++;long long r = xorshift();auto f = [&](long long x) {return (__int128_t(x) * x + r) % n;};long long x = i, y = f(x);while (true) {long long p = gcd(abs(y - x + n), n);if (p == 0 || p == n) {break;}if (p != 1) {return p;}x = f(x);y = f(f(y));}}}vector<long long> prime_factorize(long long n) {if (n == 1) {return {};}long long p = Pollard(n);if (p == n) {return {p};}vector<long long> l = prime_factorize(p);vector<long long> r = prime_factorize(n / p);for (auto x : r) {l.emplace_back(x);}sort(l.begin(), l.end());return l;}vector<long long> divisors(long long n) {if (n == 1) {return {1LL};}auto divisor_dfs = [&](auto divisor_dfs, vector<pair<long long, long long>> &p, long long t, int cur, vector<long long> &res) -> void {if (cur == p.size()) {res.emplace_back(t);return;}divisor_dfs(divisor_dfs, p, t, cur + 1, res);for (int i = 0; i < p[cur].second; i++) {t *= p[cur].first;divisor_dfs(divisor_dfs, p, t, cur + 1, res);}};vector<long long> res, pf = prime_factorize(n);vector<pair<long long, long long>> p;long long cnt = 1, now = pf[0];for (int i = 1; i < (int)pf.size(); i++) {if (pf[i] == now) {cnt++;} else {p.emplace_back(now, cnt);now = pf[i];cnt = 1;}}p.emplace_back(now, cnt);divisor_dfs(divisor_dfs, p, 1, 0, res);sort(res.begin(), res.end());return res;}} // namespace fastprimeusing namespace fastprime;template <class T>vector<pair<T, int>> RLE(vector<T> v) {vector<pair<T, int>> res;for (auto x : v) {if (res.size() == 0 || res.back().first != x) {res.emplace_back(x, 1);} else {res.back().second++;}}return res;}int main() {ld a, b;cin >> a >> b;if (b == 0.0000) {cout << "Yes" << endl;return 0;}lint ap, aq, bp, bq;if (b >= 0) {ap = a * 10000, aq = 10000;bp = b * 10000, bq = 10000;} else {b *= -1;ap = a * 10000, aq = 10000;bp = b * 10000, bq = 10000;swap(ap, aq);}Fraction A(ap, aq), B(bp, bq);if (A.q != 1) {cout << "No" << endl;return 0;}auto d = RLE(prime_factorize(A.p));for (auto [fi, se] : d) {if (B.q != 0 && se % B.q != 0) {cout << "No" << endl;return 0;}}cout << "Yes" << endl;}