原題傳送門
題面不多贅述，
對于題目給我們的要求，我們思考，其中這個gcd對整體的貢獻，由于任意兩條相鄰邊之間存在一條權值恒定的邊，也就是說，如果gcd的值大于這個值，它就不作貢獻，從而能夠對答案產生貢獻的當且僅當某一段的gcd小于這個給定的p，我們不妨將每個點的值與其索引系結，然后排序，只需要考慮所有小于p的點的貢獻，對于每個點，它的貢獻就是將它前面與其后面最長的一段滿足gcd等于該值的所有點連向它，即產生這一段的貢獻，如果任意兩個點之間的影響范圍相交，則可以直接跳出，稍微思考模擬一下即可(易證)，但是考慮到這樣一次掃描后，所有的點未必連在一個塊內，我們只需要依次將對應得點以p得權值加入即可，
//#include<bits/stdc++.h> ----萬能頭----
#include <iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<cmath>
#include<queue>
#include<list>
#include<map>
#include<unordered_map>
#include<stack>
using namespace std;
const int p = 1e9+7;
const int N = 2e5+5;
const int maxn = 1e5+10;
const long long INF = 1e18;
#define REP(i,n) for(ll i = 1; i <= n; ++i)
#define REPA(i,j,n) for(ll i = j; i <= n; ++i)
#define RREP(i,n) for(ll i = n; i >= 1; --i)
#define REPR(i,j,n) for(ll i = n; i >= j; --i)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> PII;
typedef pair<double,ll> pdi;
ll t, n, m;
ll k;
ll a[N];
bool st[N];
ll gcd(ll a,ll b){
ll res;
while(b){
res = a % b;
a = b;
b = res;
}
return a;
}
void solve(){
scanf("%lld%lld",&n,&m);
for(int i = 1; i <= n; ++i)st[i] = 0;
for(int i = 1; i <= n; ++i)scanf("%lld",&a[i]);
vector<PII> q;
ll ans = 0;
for(int i = 1; i <= n; ++i)q.push_back({a[i],i});
sort(q.begin(),q.end());
for(auto &x : q){
ll pos = x.second;
ll now_weight = x.first;
if(now_weight >= m)break;
while(pos > 1){
if(st[pos - 1])break;
if(a[pos - 1] % now_weight == 0){
ans += now_weight;
st[pos - 1] = 1;
--pos;
}
else break;
}
pos = x.second;
while(pos < n){
if(st[pos])break;
if(a[pos + 1] % now_weight == 0){
ans += now_weight;
st[pos] = 1;
++pos;
}
else break;
}
}
for(int i = 1; i < n; ++i){
if(!st[i])ans += m;
}
cout<<ans<<'\n';
}
int main() {
//ios::sync_with_stdio(0);
//cin.tie(0);
//cout.tie(0);
#ifdef ACM
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
scanf("%lld",&t);
while(t--)
solve();
fclose(stdin);
fclose(stdout);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/275508.html
標籤：其他
上一篇：2021-04-12
下一篇：C++學習