test/queue/SwagQueue-gcd.test.cpp

• View this file on GitHub
• Last update: 2023-06-06 01:28:30+09:00
• Problem: https://yukicoder.me/problems/no/1036

Depends on

• SwagQueue (lib/15-queue/SwagQueue.cpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/1036"

#include <vector>
#include <iostream>
#include <stack>
using namespace std;
#include "../../lib/15-queue/SwagQueue.cpp"

int main(void){
	cin.tie(0);ios::sync_with_stdio(false);
	long long N; cin >> N;
	vector<long long> A(N+1,1);
	for(int i = 0; i < N; ++i) cin >> A[i];
	SwagQueue<NodeGcd<long long>> swag;
	long long ans=0;
	int r=0;
	swag.push(A[0]);
	for(int i=0; i<N; i++){
		while(r<i) {
			r++;
			swag.push(A[r]);
		}
		while(r<N){
			if(swag.fold()==1) break;
			r++;
			swag.push(A[r]);
		}
		ans+=N-r;
		swag.pop();
	}
	cout << ans << endl;
}

#line 1 "test/queue/SwagQueue-gcd.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1036"

#include <vector>
#include <iostream>
#include <stack>
using namespace std;
#line 1 "lib/15-queue/SwagQueue.cpp"
/*
 * @title SwagQueue
 * @docs md/data-structure/SwagQueue.md
 */
template<class Operator> class SwagQueue{
public:
    using TypeNode = typename Operator::TypeNode;
    stack<pair<TypeNode,TypeNode>> pre,suf;

    SwagQueue() {
        // do nothing
    }
    TypeNode fold() {
        TypeNode res = Operator::unit_node;
        if(pre.size()) res = Operator::func_node(pre.top().second,res);
        if(suf.size()) res = Operator::func_node(res,suf.top().second);
        return res;
    }
    void push(TypeNode val) {
        TypeNode acc = val;
        if(suf.size()) acc = Operator::func_node(suf.top().second,val);
        suf.emplace(val,acc);
    }
    void pop() {
        if(pre.empty()) {
            TypeNode acc = Operator::unit_node;
            while(suf.size()) {
                auto [val,_] = suf.top();
                suf.pop();
                acc = Operator::func_node(val,acc);
                pre.emplace(val,acc);
            }
        }
        if(pre.size()) pre.pop();
    }
    size_t size(){
        return pre.size()+suf.size();
    }
};

template<class T> struct NodeGcd {
    using TypeNode = T;
    inline static constexpr TypeNode unit_node = 0;
    inline static constexpr TypeNode func_node(TypeNode l,TypeNode r){return r?func_node(r,l%r):l;}
};

template<class T> struct NodeComposite {
    using TypeNode = T;
    inline static constexpr TypeNode unit_node = {1,0};
    inline static constexpr TypeNode func_node(TypeNode l,TypeNode r){return {r.first*l.first,r.first*l.second+r.second};}
};
#line 8 "test/queue/SwagQueue-gcd.test.cpp"

int main(void){
	cin.tie(0);ios::sync_with_stdio(false);
	long long N; cin >> N;
	vector<long long> A(N+1,1);
	for(int i = 0; i < N; ++i) cin >> A[i];
	SwagQueue<NodeGcd<long long>> swag;
	long long ans=0;
	int r=0;
	swag.push(A[0]);
	for(int i=0; i<N; i++){
		while(r<i) {
			r++;
			swag.push(A[r]);
		}
		while(r<N){
			if(swag.fold()==1) break;
			r++;
			swag.push(A[r]);
		}
		ans+=N-r;
		swag.pop();
	}
	cout << ans << endl;
}

Back to top page