結果
| 問題 | No.1036 Make One With GCD 2 |
| ユーザー |
 WarToks
|
| 提出日時 | 2020-04-25 22:16:24 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 897 ms / 2,000 ms |
| コード長 | 20,380 bytes |
| コンパイル時間 | 1,636 ms |
| コンパイル使用メモリ | 125,576 KB |
| 最終ジャッジ日時 | 2025-01-10 01:42:57 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 41 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <complex>#include <cmath>#include <cstring>#include <deque>#include <functional>#include <map>#include <initializer_list>#include <iostream>#include <random>#include <queue>#include <string>#include <set>#include <stack>#include <tuple>#include <type_traits>#include <utility>#include <vector>template <typename S, typename T> inline bool chmin(S& a, const T b){ if(b < a){ a = b; return true; } return false; }template <typename S, typename T> inline bool chmax(S& a, const T b){ if(a < b){ a = b; return true; } return false; }template <typename T> inline bool bitUP(const T state, const unsigned int k) { return (state >> k) & 1; }inline bool isIn(int x, int y, int H, int W){ return 0 <= x and x < H and 0 <= y and y < W; }inline auto isInTheGrid(const int H, const int W){return std::bind(isIn, std::placeholders::_1, std::placeholders::_2, H, W);}namespace MyInputAndOutput{// 入力関係 (cin)class user_input{private:static constexpr unsigned int sizeOfAscii = 128;bool isBlankChar[sizeOfAscii];/* < definition of getchar >referenceMacOS : https://developer.apple.com/library/archive/documentation/System/Conceptual/ManPages_iPhoneOS/man3/getchar.3.htmlWindows : https://docs.microsoft.com/en-us/cpp/c-runtime-library/reference/getchar-nolock-getwchar-nolock?view=vs-2019Linux : https://linux.die.net/man/3/unlocked_stdioUbuntu : http://manpages.ubuntu.com/manpages/trusty/man3/getchar_unlocked.3posix.html*/#if defined(__APPLE__)#define DAGGER_GETCHAR_UNLOCKED_DAGGER getchar_unlocked#elif defined(_WIN32) || defined(_WIN64)#define DAGGER_GETCHAR_UNLOCKED_DAGGER _getchar_nolock#elif defined(__linux)#if _POSIX_C_SOURCE >= 1 || _XOPEN_SOURCE || _POSIX_SOURCE || _BSD_SOURCE || _SVID_SOURCE#define DAGGER_GETCHAR_UNLOCKED_DAGGER getchar_unlocked#else#define DAGGER_GETCHAR_UNLOCKED_DAGGER getchar#endif#else#define DAGGER_GETCHAR_UNLOCKED_DAGGER getchar#endif// 符号あり整数を getchar で読み込んで構成する (もし, 0 ~ 9 以外の文字が含まれると困る)template <typename Tp>inline void charToInteger(Tp& val) const {val = 0; int c; while(true){c = DAGGER_GETCHAR_UNLOCKED_DAGGER();if(c == EOF) return;if('-' or (not isBlankChar[c])) break;}if(c == '-'){while(true){c = DAGGER_GETCHAR_UNLOCKED_DAGGER();if(c < '0' or c > '9') break;val = 10 * val + c - '0';} val = -val;}else{if(c < '0' or c > '9') return;do{val = 10 * val + c - '0';c = DAGGER_GETCHAR_UNLOCKED_DAGGER();} while('0' <= c and c <= '9');}}// 符号なし整数を getchar で読み込んで構成する (もし, 符号付きだとバグる)template <typename Tp>inline void charToUnsignedInteger(Tp& val) const {val = 0; int c; while(true){c = DAGGER_GETCHAR_UNLOCKED_DAGGER();if(c == EOF) return;if(not isBlankChar[c]) break;}if(c < '0' or c > '9') return;do{val = 10 * val + c - '0';c = DAGGER_GETCHAR_UNLOCKED_DAGGER();} while(not (c == EOF or isBlankChar[c]));}public:constexpr user_input(void) : isBlankChar(){for(unsigned int i = 0; i < sizeOfAscii; ++i) isBlankChar[i] = false;isBlankChar[int('\n')] = true; isBlankChar[int('\t')] = true;isBlankChar[int(' ')] = true; isBlankChar[int('\v')] = true;}inline const user_input& operator >> (int& int_arg) const {charToInteger<int>(int_arg); return *this;}inline const user_input& operator >> (long long int& llint_arg) const {charToInteger<long long int>(llint_arg); return *this;}inline const user_input& operator >> (unsigned int& uint_arg) const {charToUnsignedInteger<unsigned int>(uint_arg); return *this;}inline const user_input& operator >> (unsigned long long int& ullint_arg) const {charToUnsignedInteger<unsigned long long int>(ullint_arg); return *this;}inline const user_input& operator >> (unsigned long& ulint_arg) const {charToUnsignedInteger<unsigned long>(ulint_arg); return *this;}inline const user_input& operator >> (float& float_arg) const {scanf("%f", &float_arg); return *this;}inline const user_input& operator >> (double& double_arg) const {scanf("%lf", &double_arg); return *this;}inline const user_input& operator >> (long double& ldouble_arg) const {scanf("%Lf", &ldouble_arg); return *this;}inline const user_input& operator >> (char* str_arg) const {scanf("%s", str_arg);return *this;}inline const user_input& operator >> (char& char_arg) const {do{if((char_arg = DAGGER_GETCHAR_UNLOCKED_DAGGER()) == EOF) return *this;} while(isBlankChar[int(char_arg)]);return *this;}inline const user_input& operator >> (std::string& str_arg) const {str_arg.erase();int c; while(true){c = DAGGER_GETCHAR_UNLOCKED_DAGGER();if(c == EOF) return *this;if(not isBlankChar[c]) break;}constexpr unsigned int buffer_size = 128;char buffer_input[buffer_size]; unsigned int buffer_length = 0;do{buffer_input[buffer_length++] = c;if(buffer_length == buffer_size){buffer_length = 0; str_arg.append(buffer_input, buffer_size);}c = DAGGER_GETCHAR_UNLOCKED_DAGGER();} while(c != EOF and (not isBlankChar[c]) );str_arg.append(buffer_input, buffer_length);return *this;}template <typename S, typename T>inline const user_input& operator >>(std::pair<S, T>& pair_arg) const{(*this) >> pair_arg.first >> pair_arg.second; return *this;}template <typename T>inline const user_input& operator >>(std::vector<T>& vec) const {for(T& ele : vec) (*this) >> ele;return *this;}// getchar の define の解除#undef DAGGER_GETCHAR_UNLOCKED_DAGGER}; constexpr user_input cin;void ends(void) {putchar('\0'); }void endl(void) {putchar('\n'); fflush(stdout);}void flush(void) {fflush(stdout);}constexpr char eol = '\n';// 出力関係 (cout)class user_output{public:constexpr user_output(void){}inline const user_output& operator << (const int int_arg) const{printf("%d", int_arg); return *this;}inline const user_output& operator << (const unsigned int uint_arg) const{printf("%u", uint_arg); return *this;}inline const user_output& operator << (const long long int llint_arg) const {printf("%lld", llint_arg); return *this;}inline const user_output& operator << (const unsigned long long int ullint_arg) const {printf("%llu", ullint_arg); return *this;}inline const user_output& operator << (const unsigned long ulint_arg) const {printf("%lu", ulint_arg); return *this;}inline const user_output& operator << (const float flt_arg) const {printf("%.16f", flt_arg); return *this;}inline const user_output& operator << (const double ld_arg) const {printf("%.16lf", ld_arg); return *this;}inline const user_output& operator << (const long double ld_arg) const {printf("%.16Lf", ld_arg); return *this;}inline const user_output& operator << (const char char_arg) const {putchar(char_arg); return *this;}inline const user_output& operator << (const unsigned char uchar_arg) const {putchar(uchar_arg); return *this;}inline const user_output& operator << (const char* str_arg) const {fputs(str_arg, stdout); return *this;}inline const user_output& operator << (const std::string& str_arg) const {fputs(str_arg.c_str(), stdout); return *this;}inline const user_output& operator << (void(* const func_arg)(void)) const {func_arg(); return *this;}template <typename S, typename T>inline const user_output& operator <<(const std::pair<S, T>& pair_arg) const{(*this) << pair_arg.first << ' ' << pair_arg.second; return *this;}template <typename Tp_name>inline const user_output& operator << (const std::vector<Tp_name>& vec) const {const size_t size_of_vec = vec.size();if(size_of_vec <= 0) return *this;(*this) << vec[0];for(size_t index = 1; index < size_of_vec; ++index) (*this) << ' ' << vec[index];return *this;}}; constexpr user_output cout;// その他出力関数template <typename Integer = unsigned long long int>void binary_output(const Integer value, const unsigned int length = 64){char out[length + 1];for(unsigned int i = 0, j = length - 1; i < length; ++i, --j) out[j] = ((value >> i) & 1) ? '1' : '0';out[length] = '\0'; puts(out);}template <typename InputType>void print(InputType first, InputType last, const char separate_c = ' ', const char end_c = '\n'){InputType it = first;while(true){MyInputAndOutput::cout << *it;if(++it == last){MyInputAndOutput::cout << end_c; return;}MyInputAndOutput::cout << separate_c;}}}; namespace MIO = MyInputAndOutput;namespace MyStandardLibrary{// z-algorithmtemplate <class T> std::vector<unsigned int> z_algorithm(const T &str) {const size_t n = str.size();std::vector<unsigned int> resOfCP(n); resOfCP[0] = n;int i = 1, j = 0;while (i < n) {while (i + j < n and str[j] == str[i + j]) ++j;resOfCP[i] = j;if (j == 0) { ++i; continue;}int k = 1;while (i + k < n and k + resOfCP[k] < j) resOfCP[i + k] = resOfCP[k], ++k;i += k; j -= k;}return resOfCP;}// 累乗を求める関数 : 指数部は非負整数unsigned int power(unsigned int a, unsigned long long int n, const unsigned int mod_number = 1000000007){unsigned int res = 1;while(n){if(n & 1) res = (unsigned long long int)(res) * a % mod_number;a = (unsigned long long int)(a) * a % mod_number;n >>= 1;}return res;}// 転倒数を求める関数 : 任意の Ai に対し, Ai ∈ [0, bound) であることを仮定している : O(Nlog{bound})unsigned long long int tentou(const std::vector<unsigned int>& A, const unsigned int bound){const unsigned int n = A.size();if(n <= 30){ // ある程度小さい時はナイーブの方が早いunsigned long long int res = 0;for(unsigned int i = 0; i < n; ++i) for(unsigned int j = i + 1; j < n; ++j) if(A[i] > A[j]) ++res;return res;}std::vector<unsigned int> fenwick(bound + 1, 0);unsigned long long int res = (unsigned long long int)(n) * (n - 1) >> 1;for(unsigned int i = 0; i < n; ++i){for(unsigned int x = A[i] ; x ; x -= x & (-x)) res -= fenwick[x];for(unsigned int x = A[i] + 1; x <= bound; x += x & (-x)) ++fenwick[x];}return res;}// modintクラス : 法 modulous はコンパイル時定数template <const unsigned int modulous> class modInt{private:static unsigned int power(unsigned int a, unsigned int n){unsigned int res = 1;while(n){if(n & 1) res = (unsigned long long int)(res) * a % modulous;a = (unsigned long long int)(a) * a % modulous;n >>= 1;}return res;}static unsigned int inverse(const unsigned int n_val){ return power(n_val, modulous - 2); }static unsigned int inverse_euclidean(unsigned int a){unsigned int b = modulous; long long int u = 1, v = 0;while(b){const unsigned int t = a / b;std::swap(a -= t * b, b);std::swap(u -= t * v, v);}return (u < 0) ? u + modulous : u;}public:unsigned int val;constexpr modInt(void):val(){}template <typename Integer> constexpr modInt(const Integer n_val):val(){if(n_val < 0){ const unsigned int tmp_val = (-n_val) % modulous; val = (tmp_val) ? modulous - tmp_val : 0; }else{ val = n_val % modulous; }}constexpr modInt& operator += (const modInt& other){ if((val += other.val) >= modulous) val -= modulous; return *this; }constexpr modInt& operator -= (const modInt& other){ if(val < other.val) val += modulous - other.val; else val -= other.val; return *this; }constexpr modInt& operator *= (const modInt& other){ val = static_cast<unsigned long long int>(val) * other.val % modulous; return *this; }constexpr modInt& operator /= (const modInt& other){ val = static_cast<unsigned long long int>(val) * inverse_euclidean(other.val) % modulous; return *this; }constexpr modInt operator + (const modInt& other) const { return modInt(*this) += other; }constexpr modInt operator - (const modInt& other) const { return modInt(*this) -= other; }constexpr modInt operator * (const modInt& other) const { return modInt(*this) *= other; }constexpr modInt operator / (const modInt& other) const { return modInt(*this) /= other; }constexpr modInt& operator ++ (void){ if(++val == modulous) val = 0; return *this; }constexpr modInt& operator -- (void){ if(!(val--)) val = modulous - 1; return *this; }constexpr bool operator == (const modInt& other) const { return val == other.val; }constexpr bool operator != (const modInt& other) const { return val != other.val; }constexpr modInt operator - (void) const { return modInt(val ? modulous - val : 0); }friend std::ostream& operator << (std::ostream& os, const modInt& modint_val){os << modint_val.val; return os;}};}; namespace MSL = MyStandardLibrary;// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~// グリッド上の縦横移動constexpr std::array<std::pair<int, int>, 4> dxdy = {{ {1, 0}, {-1, 0}, {0, 1}, {0, -1} }};// 型エイリアスusing unint = unsigned int;using lli = long long int;using ulli = unsigned long long int;using pii = std::pair<int, int>;#define REP(i, n) for(unsigned int i = 0; i < n; ++i)// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~using MIO::cin; using MIO::cout; using MIO::eol;// @ 要約 | スパーステーブル// => 変更のない, 冪等性の成り立つ演算( max, min, gcd ... ) に関して, 前処理を行ってクエリを高速に処理するデータ構造/// => 計算量 : 構築 O(NlogN), クエリ O(1) or O(loglog N)// @ 引数 | monodit_idempotent// -> 要件 : 冪等性 a^k = a を満たすような演算 operator() が定義されていること// : using value_type = (データ型) が定義されていること (publicで)template <class monoid_idempotent> class SparseTable{private:using element_t = typename monoid_idempotent::value_type; // データの型const unsigned int length; // 配列の長さ (データ長 n)const unsigned int log_len; // 2^k ≤ length となる最大の kconst unsigned int alloc_len; // 確保するデータの長さ = length * (k + 1)std::allocator<element_t> alloc; // アロケータelement_t* data; // 確保したデータの先頭を指すポインタ// @ 2^k ≤ x なる最大の 整数 k を返す関数static unsigned int getMSB(unsigned int x) noexcept {#ifdef __has_builtinreturn 31 - __builtin_clz(x);#elseunsigned int res = 0;if(x >> 16){x >>= 16; res += 16;}if(x >> 8) {x >>= 8; res += 8;}if(x >> 4) {x >>= 4; res += 4;}if(x >> 2) {x >>= 2; res += 2;}return res + (x >> 1);#endif}static unsigned int set_log_len(const unsigned int n){unsigned int res = 0; while((1U << res++) < n);return res - 1;}// @ 要約 : イテレーターを受け取って初期化を行うコンストラクタの補助関数 (メモリの解放等も行う)// @ 注釈 : length, log_len, alloc_len などの値が既に決定していると仮定するtemplate <class InputIterator>void initialize(InputIterator first_itr, InputIterator last_itr){data = alloc.allocate(alloc_len);std::copy(first_itr, last_itr, data);for(unsigned int prev_len = 1, prev_head = 0; prev_len< length; prev_len <<= 1){unsigned int i = prev_head, j = prev_head + prev_len, k = (prev_head += length);for(; j < prev_head; ++i, ++j, ++k) data[k] = monoid_idempotent()(data[i], data[j]);std::copy(data + i, data + j, data + k);}}public:// コンストラク by std::vectorSparseTable(const std::vector<element_t>& A): length(A.size()),log_len(set_log_len(length)),alloc_len(length * (log_len + 1)){initialize(A.cbegin(), A.cend());}~SparseTable(void){ alloc.deallocate(data, alloc_len); }// @ 区間 [l, r) (0-indexed) の値 ∑ f(ai) の 計算結果を返す関数selement_t query(const unsigned int l, const unsigned int r) const {#if trueassert(l < r);#endifconst unsigned int msb_bit = getMSB(r - l);const unsigned int pointer = length * msb_bit;//std::cout << "gcd[" << l << ", " << r << ") : " << monoid_idempotent()(data[pointer + l], data[pointer + r - (1U << msb_bit)]) << eol;return monoid_idempotent()(data[pointer + l], data[pointer + r - (1U << msb_bit)]);}};class Michel{public:using value_type = unsigned long long int;inline value_type operator()(value_type a, value_type b){while(b) std::swap(a %= b, b);return a;}};int main(void){unsigned int n; cin >> n;std::vector<unsigned long long int> A(n); cin >> A;SparseTable<Michel> ST(A);unsigned long long int res = 0;for(unsigned int l = 0, r = 0; l < n; ++l){if(l == r) ++r;if(ST.query(l, r) != 1){if(ST.query(l, n) != 1) break;unsigned int tl = r; r = n;while(r - tl > 1){const unsigned int t = (r + tl) >> 1;if(ST.query(l, t) == 1) r = t; else tl = t;}}res += n - r + 1;}cout << res << eol;return 0;}