結果
問題 | No.1036 Make One With GCD 2 |
ユーザー | suta28407928 |
提出日時 | 2020-04-25 17:06:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,535 ms / 2,000 ms |
コード長 | 3,930 bytes |
コンパイル時間 | 970 ms |
コンパイル使用メモリ | 95,600 KB |
実行使用メモリ | 15,480 KB |
最終ジャッジ日時 | 2024-09-16 13:48:36 |
合計ジャッジ時間 | 23,240 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include <iostream>#include <string>#include <cstdlib>#include <cmath>#include <vector>#include <map>#include <set>#include <algorithm>#include <queue>#include <stack>#include <functional>#include <bitset>#include <assert.h>using namespace std;typedef long long ll;typedef vector<ll> vl;typedef vector<vl> vvl;typedef vector<char> vc;typedef vector<string> vs;typedef vector<bool> vb;typedef vector<double> vd;typedef pair<ll,ll> P;typedef vector<P> vpl;typedef tuple<ll,ll,ll> tapu;#define rep(i,n) for(ll i=0; i<(n); i++)#define REP(i,a,b) for(int i=(a); i<(b); i++)#define all(x) (x).begin(), (x).end()#define rall(x) (x).rbegin(), (x).rend()const int inf = 1<<30;const ll linf = 1LL<<62;const int MAX = 510000;ll dy[8] = {0,1,0,-1,1,-1,1,-1};ll dx[8] = {1,0,-1,0,1,-1,-1,1};const double pi = acos(-1);const double eps = 1e-7;template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){if(a>b){a = b; return true;}else return false;}template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){if(a<b){a = b; return true;}else return false;}template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){cout << a << " " << b << " " << c << "\n";}const int mod = 1e9 + 7;//const int mod = 998244353;template< typename Monoid >struct SegmentTree {using F = function< Monoid(Monoid, Monoid) >;int sz;vector< Monoid > seg;const F f;const Monoid M1;SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz, M1);}void set(int k, const Monoid &x) {seg[k + sz] = x;}void build() {for(int k = sz - 1; k > 0; k--) {seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);}}void update(int k, const Monoid &x) {k += sz;seg[k] = x;while(k >>= 1) {seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);}}Monoid query(int a, int b) {Monoid L = M1, R = M1;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {if(a & 1) L = f(L, seg[a++]);if(b & 1) R = f(seg[--b], R);}return f(L, R);}Monoid operator[](const int &k) const {return seg[k + sz];}template< typename C >int find_subtree(int a, const C &check, Monoid &M, bool type) {while(a < sz) {Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);if(check(nxt)) a = 2 * a + type;else M = nxt, a = 2 * a + 1 - type;}return a - sz;}template< typename C >int find_first(int a, const C &check) {Monoid L = M1;if(a <= 0) {if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);return -1;}int b = sz;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {if(a & 1) {Monoid nxt = f(L, seg[a]);if(check(nxt)) return find_subtree(a, check, L, false);L = nxt;++a;}}return -1;}template< typename C >int find_last(int b, const C &check) {Monoid R = M1;if(b >= sz) {if(check(f(seg[1], R))) return find_subtree(1, check, R, true);return -1;}int a = sz;for(b += sz; a < b; a >>= 1, b >>= 1) {if(b & 1) {Monoid nxt = f(seg[--b], R);if(check(nxt)) return find_subtree(b, check, R, true);R = nxt;}}return -1;}};ll GCD(ll a, ll b){if(b==0) return a;else return GCD(b,a%b);}int main(){ll n; cin >> n;vl a(n); rep(i,n) cin >> a[i];SegmentTree<ll> seg(n,[](ll a, ll b){return GCD(a,b);},0);rep(i,n) seg.update(i,a[i]);ll right = 0;ll ans = 0;rep(i,n){ll gc = seg.query(i,right+1);while(right < n){gc = GCD(gc,a[right]);if(gc == 1) break;right++;}ans += n - right;if(i==right) right++;}cout << ans << endl;}