結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
|
提出日時 | 2020-04-24 21:31:16 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 790 bytes |
コンパイル時間 | 3,831 ms |
コンパイル使用メモリ | 145,844 KB |
最終ジャッジ日時 | 2025-01-09 23:14:30 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 TLE * 1 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <map>#include <set>#include <queue>#include <stack>#include <numeric>#include <bitset>#include <cmath>static const int MOD = 1000000007;using ll = long long;using u32 = uint32_t;using namespace std;template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;int main() {int n;cin >> n;vector<ll> v(n);for (auto &&k : v) scanf("%lld", &k);ll ans = 0;vector<map<ll, ll>> X(2);for (int i = 0; i < n; ++i) {int now = i&1, nxt = now^1;X[now].clear();for (auto &&j : X[nxt]) {X[now][__gcd(j.first, v[i])] += j.second;}X[now][v[i]]++;ans += X[now][1];}cout << ans << "\n";return 0;}