結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 21:52:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 809 ms / 2,000 ms |
コード長 | 3,872 bytes |
コンパイル時間 | 1,801 ms |
コンパイル使用メモリ | 173,336 KB |
実行使用メモリ | 19,092 KB |
最終ジャッジ日時 | 2024-09-16 13:14:32 |
合計ジャッジ時間 | 12,884 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>int ri() {int n;scanf("%d", &n);return n;}#define MOD 1000000007template<int mod>struct ModInt{int x;ModInt():x(0){}ModInt(long long y):x(y>=0?y%mod:(mod-(-y)%mod)%mod){}ModInt &operator+=(const ModInt &p){if((x+=p.x)>=mod)x-=mod;return *this;}ModInt &operator-=(const ModInt &p){if((x+=mod-p.x)>=mod)x-=mod;return *this;}ModInt &operator*=(const ModInt &p){x=(int)(1LL*x*p.x%mod);return *this;}ModInt &operator/=(const ModInt &p){*this*=p.inverse();return *this;}ModInt &operator^=(long long p){ModInt res = 1;for (; p; p >>= 1) {if (p & 1) res *= *this;*this *= *this;}return *this = res;}ModInt operator-()const{return ModInt(-x);}ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;}ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;}ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;}ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;}ModInt operator^(long long p)const{return ModInt(*this)^=p;}bool operator==(const ModInt &p)const{return x==p.x;}bool operator!=(const ModInt &p)const{return x!=p.x;}explicit operator int() const { return x; } // added by QCFiumModInt operator=(const int p) {x = p; return ModInt(*this);} // added by QCFiumModInt inverse()const{int a=x,b=mod,u=1,v=0,t;while(b>0){t=a/b;a-=t*b;std::swap(a,b);u-=t*v;std::swap(u,v);}return ModInt(u);}friend std::ostream &operator<<(std::ostream &os,const ModInt<mod> &p){return os<<p.x;}friend std::istream &operator>>(std::istream &is,ModInt<mod> &a){long long x;is>>x;a=ModInt<mod>(x);return (is);}};typedef ModInt<MOD> mint;struct MComb {std::vector<mint> fact;std::vector<mint> inversed;MComb(int n) { // O(n+log(mod))fact = std::vector<mint>(n+1,1);for (int i = 1; i <= n; i++) fact[i] = fact[i-1]*mint(i);inversed = std::vector<mint>(n+1);inversed[n] = fact[n] ^ (MOD-2);for (int i = n - 1; i >= 0; i--) inversed[i]=inversed[i+1]*mint(i+1);}mint ncr(int n, int r) {return (fact[n] * inversed[r] * inversed[n-r]);}mint npr(int n, int r) {return (fact[n] * inversed[n-r]);}mint nhr(int n, int r) {assert(n+r-1 < (int)fact.size());return ncr(n+r-1, r);}};int64_t gcd(int64_t a, int64_t b) {while (a && b) {if (a > b) a %= b;else b %= a;}return a + b;}struct SWAG {std::vector<int64_t> left_sum;std::vector<int64_t> right;std::vector<int64_t> right_sum;void push_back(int64_t a) {right.push_back(a);right_sum.push_back(right_sum.size() ? gcd(right_sum.back(), a) : a);}void pop_back() { // just after push_backright.pop_back();right_sum.pop_back();}void pop_front() {if (left_sum.size()) left_sum.pop_back();else {int r0 = (right.size() + 1) / 2;if (r0 > 1) {left_sum.push_back(right[r0 - 1]);for (int i = r0 - 2; i; i--) left_sum.push_back(gcd(right[i], left_sum.back()));}right.erase(right.begin(), right.begin() + r0);right_sum.resize(right.size());if (right.size()) {right_sum[0] = right[0];for (int i = 1; i < (int) right.size(); i++) right_sum[i] = gcd(right_sum[i - 1], right[i]);}}}int64_t get() {int64_t cur = 0;if (left_sum.size()) cur = gcd(cur, left_sum.back());if (right_sum.size()) cur = gcd(cur, right_sum.back());return cur;}};int main() {int n = ri();int64_t a[n];for (auto &i : a) scanf("%" SCNd64, &i);int l = 0;int r = 0;SWAG swag;int64_t res = 0;for (int i = 0; i < n; i++) {if (l == i - 1) {l++;if (r == l - 1) r++;else swag.pop_front();}while (r < n) {swag.push_back(a[r]);if (swag.get() == 1) {swag.pop_back();break;}r++;}res += n - r;}printf("%" PRId64 "\n", res);return 0;}