結果
問題 | No.2051 Divide |
ユーザー | nouka28 |
提出日時 | 2023-12-08 22:18:15 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 8,062 bytes |
コンパイル時間 | 6,663 ms |
コンパイル使用メモリ | 338,100 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-27 03:13:47 |
合計ジャッジ時間 | 7,908 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
ソースコード
#pragma region template #include<bits/stdc++.h> using namespace std; //other #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; //tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> s; #include<atcoder/all> using namespace atcoder; #include "atcoder/modint.hpp" using mint = atcoder::modint998244353; using mint2 = atcoder::modint1000000007; // using mint=modint; #define int long long #define pb push_back #define eb emplace_back #define ep emplace #define len(a) (int)a.size() #define BIT(a,b) ((a)>>(b)&1) #define endl "\n" #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") //using using ll=long long; using ld=long double; using ull=unsigned long long; using uint=unsigned; using pcc=pair<char,char>; using pii=pair<int,int>; using pll=pair<ll,ll>; using pdd=pair<ld,ld>; using vi=vector<int>; using vl=vector<ll>; using vvi=vector<vi>; using vvl=vector<vl>; using vvvi=vector<vvi>; using vvvl=vector<vvl>; template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>; template<class T>using pqmax=priority_queue<T>; template<typename T>int chmax(T &a,T b){if(a<b){a=b;return true;}return false;} template<typename T>int chmin(T &a,T b){if(a>b){a=b;return true;}return false;} const ll LINF=0x1fffffffffffffff; const int INF=0x3fffffff; const int MOD=998244353; const int MOD2=1000000007; const ld PI=3.1415926535897932384626433832795028841971; const ld DINF=numeric_limits<ld>::infinity(); const ld EPS=1e-9; const ll di[]={0,1,0,-1,1,-1,1,-1}; const ll dj[]={1,0,-1,0,1,1,-1,-1}; template<class T> constexpr auto min(T a,T b,T c){ return min(a,min(b,c)); } template<class... T> constexpr auto min(T... a){ return min(initializer_list<common_type_t<T...>>{a...}); } template<class T> constexpr auto max(T a,T b,T c){ return max(a,max(b,c)); } template<class... T> constexpr auto max(T... a){ return max(initializer_list<common_type_t<T...>>{a...}); } #define overload4(_1,_2,_3,_4,name,...) name #define overload3(_1,_2,_3,name,...) name #define rep1(n) for(ll i=0;i<n;++i) #define rep2(i,n) for(ll i=0;i<n;++i) #define rep3(i,a,b) for(ll i=a;i<b;++i) #define rep4(i,a,b,c) for(ll i=a;i<b;i+=c) #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #define rrep1(n)for(ll i=n;i--;) #define rrep2(i,n)for(ll i=n;i--;) #define rrep3(i,a,b)for(ll i=b;i-->(a);) #define rrep4(i,a,b,c)for(ll=(a)+((b)-(a)-1)/(c)*(c);i>=(a);i-=c) #define rrep(...) overload4(__VA_ARGS__,rrpe4,rrep3,rrep2,rrep1)(__VA_ARGS__) #define all1(i) begin(i),end(i) #define all2(i,a) begin(i),begin(i)+a #define all3(i,a,b) begin(i)+a,begin(i)+b #define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__) #define sum(...) accumulate(all(__VA_ARGS__),0LL) #define dsum(...) accumulate(all(__VA_ARGS__),0.0L) #define Msum(...) accumulate(all(__VA_ARGS__),0_M) #define elif else if #define INT(...) int __VA_ARGS__;input(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;input(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__;input(__VA_ARGS__) #define STR(...) string __VA_ARGS__;input(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;input(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;input(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;input(__VA_ARGS__) //io //in void scan(){} void scan(signed &a){cin>>a;} void scan(unsigned &a){cin>>a;} void scan(long& a){cin>>a;} void scan(long long& a){cin>>a;} void scan(unsigned long long&a){cin>>a;} void scan(char& a){cin>>a;} void scan(float& a){cin>>a;} void scan(double& a){cin>>a;} void scan(long double& a){cin>>a;} void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++){ int b; scan(b); a[i] = b; } } void scan(char a[]){ scanf("%s", a); } void scan(string& a){cin>>a;} template<class T> void scan(vector<T>&); template<class T, int size> void scan(array<T, size>&); template<class T, class L> void scan(pair<T, L>&); template<class T, int size> void scan(T(&)[size]); template<class T> void scan(vector<T>& a){ for(auto&& i : a) scan(i); } template<class T> void scan(deque<T>& a){ for(auto&& i : a) scan(i); } template<class T, int size> void scan(array<T, size>& a){ for(auto&& i : a) scan(i); } template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); } template<class T, int size> void scan(T (&a)[size]){ for(auto&& i : a) scan(i); } template<class T> void scan(T& a){ cin >> a; } void input(){} template<class Head,class...Tail> void input(Head& head,Tail&... tail){scan(head);input(tail...);} //out void puts(){ putchar(' '); } void puts(bool a){ printf("%d", a); } void puts(signed a){ printf("%d", a); } void puts(unsigned a){ printf("%u", a); } void puts(long a){ printf("%ld", a); } void puts(long long a){ printf("%lld", a); } void puts(unsigned long long a){ printf("%llu", a); } void puts(char a){ printf("%c", a); } void puts(char a[]){ printf("%s", a); } // void puts(const char a[]){ printf("%s", a); } void puts(float a){ printf("%.15f", a); } void puts(double a){ printf("%.15f", a); } void puts(long double a){ printf("%.15Lf", a); } void puts(const string& a){ for(auto&& i : a) puts(i); } template<class T> void puts(const complex<T>& a){ if(a.real() >= 0) puts('+'); puts(a.real()); if(a.imag() >= 0) puts('+'); puts(a.imag()); puts('i'); } template<class T> void puts(const vector<T>&); template<class T, int size> void puts(const array<T, size>&); template<class T, class L> void puts(const pair<T, L>& p); template<class T, int size> void puts(const T (&)[size]); template<class T> void puts(const vector<T>& a){ if(a.empty()) return; puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template<class T> void puts(const deque<T>& a){ if(a.empty()) return; puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template<class T> void puts(const set<T>& a){ if(a.empty()) return; puts(*a.begin()); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template<class T> void puts(const multiset<T>& a){ if(a.empty()) return; puts(*a.begin()); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template<class T, int size> void puts(const array<T, size>& a){ puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } } template<class T, class L> void puts(const pair<T, L>& p){ putchar('(');puts(p.first); putchar(' '); puts(p.second); putchar(')');} template<class T, int size> void puts(const T (&a)[size]){ puts(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); puts(*i); } } template<class T> void puts(const T& a){ cout << a; } int print(){ putchar('\n'); return 0; } template<class T> int print(const T& t){ puts(t); putchar('\n'); return 0; } template<class Head, class... Tail> int print(const Head& head, const Tail&... tail){ puts(head); putchar(' '); print(tail...); return 0; } #pragma endregion #pragma region commonly used int digitsum(string s){ int res=0; rep(i,(int)s.size()){ res+=s[i]-'0'; } return res; } //乱数系 random_device rnd; mt19937 mt(rnd()); const long long MT_MAX=1e15; uniform_int_distribution<long long> rd(0,MT_MAX); double randd(){ return 1.0*rd(mt)/MT_MAX; } long long randint(long long a,long long b){ // [a,b]の乱数を生成 return a+rd(mt)%(b-a+1); } #pragma endregion vector<int> prime_fac_vec(int n) { vector<int> res; for (int i = 2; i * i <= n; i++) { while (n % i == 0) { res.push_back(i); n /= i; } } if (n != 1) res.push_back(n); return res; } map<int,int> prime_fac_map(int n) { map<int,int> res; for (int i = 2; i * i <= n; i++) { while (n % i == 0) { res[i]++; n /= i; } } if (n != 1) res[n]++; return res; } signed main(){ INT(a,b); int ans=1; auto ma=prime_fac_map(a),mb=prime_fac_map(b); for(auto e:ma){ ans*=max(0,e.second-mb[e.first]+1); } for(auto e:mb){ if(!ma[e.first])ans=0; } print(ans); }