結果
問題 | No.1224 I hate Sqrt Inequality |
ユーザー |
![]() |
提出日時 | 2020-09-11 21:23:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 15,009 bytes |
コンパイル時間 | 8,266 ms |
コンパイル使用メモリ | 387,076 KB |
最終ジャッジ日時 | 2025-01-14 09:51:25 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 |
ソースコード
////////////////////////////////////////////////////////////////////////////////// Give me AC!!! //////////////////////////////////////////////////////////////////////////////////#include <iostream>#include <random>#include <cmath>#include <limits>#include <iostream>#include <bits/stdc++.h>#include <boost/multiprecision/cpp_int.hpp>using namespace std;namespace mp = boost::multiprecision;using namespace mp;using ull = __int128;using ll = long long;using cll = cpp_int;using Graph = vector<vector<int>>;#define REP(i,n) for(ll i=0;i<(ll)(n);i++)#define REPD(i,n) for(ll i=n-1;i>=0;i--)#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)//xにはvectorなどのコンテナ#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく#define MAX(x) *max_element(ALL(x)) //最大値を求める#define MIN(x) *min_element(ALL(x)) //最小値を求める#define PQ priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>>#define INF 1000000000000 //10^12:極めて大きい値,∞#define PB push_back //vectorヘの挿入#define MP make_pair //pairのコンストラクタ#define F first //pairの一つ目の要素#define S second //pairの二つ目の要素#define coutY cout<<"YES"<<endl#define couty cout<<"Yes"<<endl#define coutN cout<<"NO"<<endl#define coutn cout<<"No"<<endl#define coutdouble(a,b) cout << fixed << setprecision(a) << double(b) ;#define vi(a,b) vector<int> a(b)#define vl(a,b) vector<ll> a(b)#define vs(a,b) vector<string> a(b)#define vll(a,b,c) vector<vector<ll>> a(b, vector<ll>(c));#define intque(a) queue<int> a;#define llque(a) queue<ll> a;#define intque2(a) priority_queue<int, vector<int>, greater<int>> a;#define llque2(a) priority_queue<ll, vector<ll>, greater<ll>> a;#define pushback(a,b) a.push_back(b)#define mapii(M1) map<int, int> M1;#define cou(v,x) count(v.begin(), v.end(), x)#define mapll(M1) map<ll,ll> M1;#define mapls(M1) map<ll, string> M1;#define mapsl(M1) map<string, ll> M1;#define twolook(a,l,r,x) lower_bound(a+l, a+r, x) - a#define sor(a) sort(a.begin(), a.end())#define rever(a) reverse(a.begin(),a.end())#define rep(i,a) for(ll i=0;i<a;i++)#define vcin(n) for(ll i=0;i<ll(n.size());i++) cin>>n[i]#define vcout(n) for(ll i=0;i<ll(n.size());i++) cout<<n[i]#define vcin2(n) rep(i,ll(n.size())) rep(j,ll(n.at(0).size())) cin>>n[i][j]//const ll mod = 998244353;//const ll MOD = 998244353;const ll MOD = 9989123;const ll mod = 9989123;constexpr ll MAX = 5000000;//const ll _max = 9223372036854775807;const ll _max = 1223372036854775807;ll fac[MAX],finv[MAX],inv[MAX];// テーブルを作る前処理void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}// 二項係数計算long long COM(int n, int k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}int modPow(long long a, long long n, long long p) {if (n == 0) return 1; // 0乗にも対応する場合if (n == 1) return a % p;if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;long long t = modPow(a, n / 2, p);return (t * t) % p;}ll clocks(ll a,ll b,ll c){return a*3600+b*60+c;}ll divup(ll b,ll d){if(b%d==0){return b/d;}else{return b/d+1;}}struct UnionFind {vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化for(int i = 0; i < N; i++) par[i] = i;}int root(int x) { // データxが属する木の根を再帰で得る:root(x) = {xの木の根}if (par[x] == x) return x;return par[x] = root(par[x]);}void unite(int x, int y) { // xとyの木を併合int rx = root(x); //xの根をrxint ry = root(y); //yの根をryif (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのままpar[rx] = ry; //xとyの根が同じでない(=同じ木にない)時:xの根rxをyの根ryにつける}bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返すint rx = root(x);int ry = root(y);return rx == ry;}};struct Edge {int to; // 辺の行き先int weight; // 辺の重みEdge(int t, int w) : to(t), weight(w) { }};using Graphw = vector<vector<Edge>>;ll zero(ll a){return max(ll(0),a);}template< typename T >struct FormalPowerSeries : vector< T > {using vector< T >::vector;using P = FormalPowerSeries;using MULT = function< P(P, P) >;static MULT &get_mult() {static MULT mult = nullptr;return mult;}static void set_fft(MULT f) {get_mult() = f;}void shrink() {while(this->size() && this->back() == T(0)) this->pop_back();}P operator+(const P &r) const { return P(*this) += r; }P operator+(const T &v) const { return P(*this) += v; }P operator-(const P &r) const { return P(*this) -= r; }P operator-(const T &v) const { return P(*this) -= v; }P operator*(const P &r) const { return P(*this) *= r; }P operator*(const T &v) const { return P(*this) *= v; }P operator/(const P &r) const { return P(*this) /= r; }P operator%(const P &r) const { return P(*this) %= r; }P &operator+=(const P &r) {if(r.size() > this->size()) this->resize(r.size());for(int i = 0; i < r.size(); i++) (*this)[i] += r[i];return *this;}P &operator+=(const T &r) {if(this->empty()) this->resize(1);(*this)[0] += r;return *this;}P &operator-=(const P &r) {if(r.size() > this->size()) this->resize(r.size());for(int i = 0; i < r.size(); i++) (*this)[i] -= r[i];shrink();return *this;}P &operator-=(const T &r) {if(this->empty()) this->resize(1);(*this)[0] -= r;shrink();return *this;}P &operator*=(const T &v) {const int n = (int) this->size();for(int k = 0; k < n; k++) (*this)[k] *= v;return *this;}P &operator*=(const P &r) {if(this->empty() || r.empty()) {this->clear();return *this;}assert(get_mult() != nullptr);return *this = get_mult()(*this, r);}P &operator%=(const P &r) {return *this -= *this / r * r;}P operator-() const {P ret(this->size());for(int i = 0; i < this->size(); i++) ret[i] = -(*this)[i];return ret;}P &operator/=(const P &r) {if(this->size() < r.size()) {this->clear();return *this;}int n = this->size() - r.size() + 1;return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev(n);}P pre(int sz) const {return P(begin(*this), begin(*this) + min((int) this->size(), sz));}P operator>>(int sz) const {if(this->size() <= sz) return {};P ret(*this);ret.erase(ret.begin(), ret.begin() + sz);return ret;}P operator<<(int sz) const {P ret(*this);ret.insert(ret.begin(), sz, T(0));return ret;}P rev(int deg = -1) const {P ret(*this);if(deg != -1) ret.resize(deg, T(0));reverse(begin(ret), end(ret));return ret;}P diff() const {const int n = (int) this->size();P ret(max(0, n - 1));for(int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i);return ret;}P integral() const {const int n = (int) this->size();P ret(n + 1);ret[0] = T(0);for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1);return ret;}// F(0) must not be 0P inv(int deg = -1) const {assert(((*this)[0]) != T(0));const int n = (int) this->size();if(deg == -1) deg = n;P ret({T(1) / (*this)[0]});for(int i = 1; i < deg; i <<= 1) {ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1);}return ret.pre(deg);}// F(0) must be 1P log(int deg = -1) const {assert((*this)[0] == 1);const int n = (int) this->size();if(deg == -1) deg = n;return (this->diff() * this->inv(deg)).pre(deg - 1).integral();}P sqrt(int deg = -1) const {const int n = (int) this->size();if(deg == -1) deg = n;if((*this)[0] == T(0)) {for(int i = 1; i < n; i++) {if((*this)[i] != T(0)) {if(i & 1) return {};if(deg - i / 2 <= 0) break;auto ret = (*this >> i).sqrt(deg - i / 2) << (i / 2);if(ret.size() < deg) ret.resize(deg, T(0));return ret;}}return P(deg, 0);}P ret({T(1)});T inv2 = T(1) / T(2);for(int i = 1; i < deg; i <<= 1) {ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2;}return ret.pre(deg);}// F(0) must be 0P exp(int deg = -1) const {assert((*this)[0] == T(0));const int n = (int) this->size();if(deg == -1) deg = n;P ret({T(1)});for(int i = 1; i < deg; i <<= 1) {ret = (ret * (pre(i << 1) + T(1) - ret.log(i << 1))).pre(i << 1);}return ret.pre(deg);}P pow(int64_t k, int deg = -1) const {const int n = (int) this->size();if(deg == -1) deg = n;for(int i = 0; i < n; i++) {if((*this)[i] != T(0)) {T rev = T(1) / (*this)[i];P C(*this * rev);P D(n - i);for(int j = i; j < n; j++) D[j - i] = C[j];D = (D.log() * k).exp() * (*this)[i].pow(k);P E(deg);if(i * k > deg) return E;auto S = i * k;for(int j = 0; j + S < deg && j < D.size(); j++) E[j + S] = D[j];return E;}}return *this;}T eval(T x) const {T r = 0, w = 1;for(auto &v : *this) {r += w * v;w *= x;}return r;}};//aはbの何乗以下かを満たす数の内最大の物,(a,10)はaの桁数ll expless(ll a,ll b){ll k=0;ll o=1;while(a>=o){k++;o=o*b;}return k;}//aをb進法で表す//b進法のaを10進法に直すll tenbase(ll a,ll b){ll c=expless(a,10);ll ans=0;ll k=1;for(int i=0;i<c;i++){ans+=(a%10)*k;k=k*b;a=a/10;}return ans;}vector<pair<long long, long long> > prime_factorize(long long N) {vector<pair<long long, long long> > res;for (long long a = 2; a * a <= N; ++a) {if (N % a != 0) continue;long long ex = 0; // 指数// 割れる限り割り続けるwhile (N % a == 0) {++ex;N /= a;}// その結果を pushres.push_back({a, ex});}// 最後に残った数についてif (N != 1) res.push_back({N, 1});return res;}ll atll(ll a,ll b){b++;ll c=expless(a,10);ll d=c-b;ll f=1;for(int i=0;i<d;i++){f=f*10;}a=(a/f);return a%10;}//aがbで何回割り切るかll exp(ll a,ll b){ll ans=0;while(a%b==0){a=a/b;ans++;}return ans;}const int dx[4] = {1, 0, -1, 0};const int dy[4] = {0, 1, 0, -1};const int X[6]={1,1,0,-1,-1,0};const int Y[6]={0,1,1,0,-1,-1};template<typename T>vector<T> smallest_prime_factors(T n) {vector<T> spf(n + 1);for (int i = 0; i <= n; i++) spf[i] = i;for (T i = 2; i * i <= n; i++) {// 素数だったらif (spf[i] == i) {for (T j = i * i; j <= n; j += i) {// iを持つ整数かつまだ素数が決まっていないならif (spf[j] == j) {spf[j] = i;}}}}return spf;}vector<pair<ll,ll>> factolization(ll x, vector<ll> &spf) {vector<pair<ll,ll>> ret;ll p;ll z;while (x != 1) {p=(spf[x]);z=0;while(x%p==0){z++;x /= p;}ret.push_back({p, z});}return ret;}vector<bool> is;vector<long long int> prime_(ll n){is.resize(n+1, true);is[0] = false;is[1] = false;vector<long long int> primes;for (int i=2; i<=n; i++) {if (is[i] == true){primes.push_back(i);for (int j=i*2; j<=n; j+=i){is[j] = false;}}}return primes;}vector<ll> dijkstra(ll f,ll n,vector<vector<vector<ll>>>& edge){//最短経路としてどの頂点が確定済みかをチェックする配列vector<ll> confirm(n,false);//それぞれの頂点への最短距離を保存する配列//始点は0,始点以外はINFで最短距離を初期化するvector<ll> mincost(n,INF);mincost[f]=0;//確定済みの頂点の集合から伸びる辺を伝ってたどり着く頂点の始点からの距離を短い順に保存するPriority queuePQ mincand;mincand.push({mincost[f],f});//mincandの要素がゼロの時、最短距離を更新できる頂点がないことを示すwhile(!mincand.empty()){//最短距離でたどり着くと思われる頂点を取り出すvector<ll> next=mincand.top();mincand.pop();//すでにその頂点への最短距離が確定済みの場合は飛ばすif(confirm[next[1]]) continue;//確定済みではない場合は確定済みにするconfirm[next[1]]=true;//その確定済みの頂点から伸びる辺の情報をとってくる(参照の方が速い)、lは辺の本数vector<vector<ll>>& v=edge[next[1]];ll l=SIZE(v);REP(i,l){//辺の先が確定済みなら更新する必要がない((✳︎2)があれば十分なので(✳︎1)は実はいらない)if(confirm[v[i][0]]) continue; //(✳︎1)//辺の先のmincost以上の場合は更新する必要がない(辺の先が確定済みの時は満たす)if(mincost[v[i][0]]<=next[0]+v[i][1]) continue; //(✳︎2)//更新mincost[v[i][0]]=next[0]+v[i][1];//更新した場合はその頂点が(確定済みでない頂点の中で)最短距離になる可能性があるのでmincandに挿入mincand.push({mincost[v[i][0]],v[i][0]});}}return mincost;}ll so(ll a){ll ans=0;if(a==0){return 0;}while(a%2==0){a/=2;ans++;}return ans;}ll HOM(ll n,ll r){return COM(n+r-1,r);}ll binary(ll bina){ll ans = 0;for (ll i = 0; bina>0 ; i++){ans = ans+(bina%2)*pow(10,i);bina = bina/2;}return ans;}int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);cout << fixed << setprecision(10);ll a,b;cin>>a>>b;b/=gcd(a,b);while(b%2==0){b/=2;}while(b%5==0){b/=5;}if(b!=1){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}