結果
問題 |
No.1036 Make One With GCD 2
|
ユーザー |
|
提出日時 | 2020-04-25 17:40:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 751 bytes |
コンパイル時間 | 1,876 ms |
コンパイル使用メモリ | 177,748 KB |
実行使用メモリ | 7,296 KB |
最終ジャッジ日時 | 2024-11-07 10:52:21 |
合計ジャッジ時間 | 19,789 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 TLE * 1 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; using ll = long long ; using P = pair<int,int> ; const int INF = 1e9; const int MOD = 1000000007; ll gcd(ll i,ll j){ if(j == 0) return i; return gcd(j,i%j); } int main(){ int n; cin >> n; vector<ll> a(n); rep(i,n) cin >> a[i]; ll ans = 0; map<ll,ll> dp1; map<ll,ll> dp2; dp1[a[0]] = 1; if(a[0] ==1) ++ans; for(int i=1;i<n;i++){ for(auto k:dp1){ dp2[gcd(k.first,a[i])] += k.second; } dp2[a[i]] ++; ans += dp2[1]; swap(dp1,dp2); map<ll,ll> empty; swap(empty,dp2); //cout << ans << endl; } cout << ans << endl; return 0; }