結果
問題 | No.990 N×Mマス計算(Kの倍数) |
ユーザー | azz |
提出日時 | 2020-02-14 22:23:46 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,293 bytes |
コンパイル時間 | 2,357 ms |
コンパイル使用メモリ | 198,868 KB |
実行使用メモリ | 14,624 KB |
最終ジャッジ日時 | 2024-04-27 19:48:21 |
合計ジャッジ時間 | 6,887 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
13,760 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 3 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 20 ms
6,944 KB |
testcase_11 | WA | - |
testcase_12 | TLE | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
ソースコード
#include <bits/stdc++.h> using namespace std; # define REP(i,n) for (int i=0;i<(n);++i) # define rep(i,a,b) for(int i=a;i<(b);++i) # define all(v) v.begin(),v.end() # define showVector(v) REP(i,v.size()){cout << (v[i]) << " ";} cout << endl; template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;} template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;} typedef long long int ll; typedef pair<ll,ll> P_ii; typedef pair<double,double> P_dd; template<class T> vector<T> make_vec(size_t a){ return vector<T>(a); } template<class T, class... Ts> auto make_vec(size_t a, Ts... ts){ return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;} template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){ for(auto &e:t) fill_v(e,v); } ll gcd(ll a, ll b) { if(a < b) swap(a,b); if(b == 0) return a; return gcd(b, a % b); } ll lcm(ll a, ll b){ ll g = gcd(a,b); return (a/g)*b; } // 素数判定 O(√n) bool is_prime(int n){ for(int i = 2; i * i <= n; i++){ if(n % i == 0) return false; } return true; } // 約数列挙 O(√n) vector<ll> divisor(ll n){ vector<ll> res; for(ll i = 1; i * i <= n; i++){ if(n % i == 0){ res.push_back(i); if(i != n / i) res.push_back(n / i); } } return res; } map<ll, ll> prime_factorize(ll n) { map<ll, ll> res; for (ll p = 2; p * p <= n; ++p) { if (n % p != 0) continue; ll num = 0; while (n % p == 0) { ++num; n /= p; } res[p] = num; } if (n != 1) res[n] = 1; return res; } // auto mod int // https://youtu.be/L8grWxBlIZ4?t=9858 // https://youtu.be/ERZuLAxZffQ?t=4807 : optimize // https://youtu.be/8uowVvQ_-Mo?t=1329 : division const int mod = 1000000007; struct mint { ll x; // typedef long long ll; mint(ll x=0):x(x%mod){} mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint a) const { mint res(*this); return res+=a; } mint operator-(const mint a) const { mint res(*this); return res-=a; } mint operator*(const mint a) const { mint res(*this); return res*=a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod-2); } mint& operator/=(const mint a) { return (*this) *= a.inv(); } mint operator/(const mint a) const { mint res(*this); return res/=a; } }; const int MOD = 1000000007; const int inf=1e9+7; const ll longinf=1LL<<60 ; void addM(ll &a, ll b) { a += b; if (a >= MOD) a -= MOD; } void mulM(ll &a, ll b) { a = ((a%MOD)*(b%MOD))%MOD ; } ll powM(ll a,ll b) { ll ret = 1; ll tmp = a; while(b>0) { if((b&1)==1) ret = (ret * tmp) % MOD; tmp = (tmp * tmp) % MOD; b = b >> 1; } return ret; } // mod. m での a の逆元 a^{-1} を計算する ll modinv(ll a, ll m) { ll b = m, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } // ラングレンス圧縮 vector<pair<char, int>> rang_com(string s){ vector<pair<char, int>> ret; string t = s; t.erase(unique(all(t)), t.end()); int now = 0; int pre = 0; for(auto ct : t){ while(now < s.size() && s[now] == ct) now++; if(ret.size() == 0){ ret.push_back({ct, now}); } else { ret.push_back({ct, now - pre}); } pre = now; } return ret; } int main(void) { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; ll K; cin >> K; char op; cin >> op; vector<ll> a(N), b(M); REP(i, M) cin >> b[i]; REP(i, N) cin >> a[i]; ll ans = 0; if(op == '+'){ REP(i, M) b[i] %= K; sort(all(b)); REP(i, N){ ll val = (K - a[i] % K) % K; ans += upper_bound(all(b), val) - lower_bound(all(b), val); } } else { auto pf = prime_factorize(K); map<vector<int>, int> mp1, mp2; REP(i, M){ auto pfb = prime_factorize(b[i]); vector<int> vec; for(auto m : pf){ vec.push_back(pfb[m.first]); } mp1[vec]++; } REP(i, N){ auto pfa = prime_factorize(a[i]); vector<int> vec; for(auto m : pf){ vec.push_back(pfa[m.first]); } mp2[vec]++; } vector<int> vec; for(auto m : pf) vec.push_back(m.second); for(auto m1 : mp1){ auto v1 = m1.first; for(auto m2 : mp2){ auto v2 = m2.first; bool chk = true; REP(i, vec.size()){ if(vec[i] > v1[i] + v2[i]){ chk = false; break; } } if(chk) ans += m1.second * m2.second; } } } cout << ans << endl; return 0; }