NC15557. 连续区间的最大公约数
描述
输入描述
第一行一个数T表示数据组数
第二行一个数n
接下来一行n个数,a1,a2,...,an
接下一行一个数q
接下来一行2个数l和r。
输出描述
首先输出一行“Case #:t”,t代表当前是第几组数据。
接下来q行，每行输出2个数，第一个是gcd(al,al+1,...,ar),
第二个是区间[l,r]的子区间中(l<=l'<=r'<=r)满足gcd(al,al+1,...,ar) = gcd(al',al'+1,...ar')的子区间个数。
示例1
输入:
2 5 1 2 4 6 7 4 1 5 2 4 3 4 4 4 5 1 2 4 2 1 6 1 1 1 3 2 2 2 3 2 4 3 3
输出:
Case #1: 1 8 2 4 2 1 6 1 Case #2: 1 1 1 3 2 1 2 2 2 5 4 1
C++14(g++5.4) 解法, 执行用时: 866ms, 内存消耗: 114636K, 提交时间: 2019-07-28 16:06:01
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define LL long long
#define pb emplace_back
#define pii pair<int, int>
const int N = 1e5 + 5;
int T, n, q, a[N], L[N], R[N], d[N], cnt;
LL ans[N];
vector<int> vc[N], p[N*20];
vector<LL> sum[N*20];
map<int, int> mp, _p, mmp;
int main() {
scanf("%d", &T);
for(int cs = 1; cs <= T; ++cs) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
scanf("%d", &q);
for (int i = 1; i <= q; ++i) {
scanf("%d %d", &L[i], &R[i]);
vc[R[i]].pb(i);
}
cnt = 0;
for (int i = 1; i <= n; ++i) {
for (auto it : mp) {
int g = __gcd(it.fi, a[i]);
if(_p.find(g) == _p.end()) _p[g] = it.se;
}
if(_p.find(a[i]) == _p.end()) _p[a[i]] = i;
mp = _p;
_p.clear();
vector<pii> tmp;
for (auto it : mp) tmp.pb(it.se, it.fi);
for (int j = 0; j < tmp.size(); ++j) {
if(j+1 == tmp.size()) tmp[j].fi = i;
else tmp[j].fi = tmp[j+1].fi-1;
int now;
if(mmp.find(tmp[j].se) == mmp.end()) {
mmp[tmp[j].se] = ++cnt;
now = cnt;
}
else now = mmp[tmp[j].se];
p[now].pb(tmp[j].fi);
sum[now].pb(sum[now].size()==0?tmp[j].fi:sum[now].back()+tmp[j].fi);
}
for (int x : vc[i]) {
int l = L[x];
int t = lower_bound(tmp.begin(), tmp.end(), pii{l, 0})-tmp.begin();
d[x] = tmp[t].se;
int pp = mmp[d[x]];
t = lower_bound(p[pp].begin(), p[pp].end(), l)-p[pp].begin();
if(t-1>=0) ans[x] = sum[pp].back()-sum[pp][t-1]-(sum[pp].size()-t)*1LL*(l-1);
else ans[x] = sum[pp].back()-sum[pp].size()*1LL*(l-1);
}
}
printf("Case #%d:\n", cs);
for (int i = 1; i <= q; ++i) printf("%d %lld\n", d[i], ans[i]);
for (auto it : mmp) p[it.se].clear(), sum[it.se].clear();
mmp.clear();
mp.clear();
for (int i = 1; i <= n; ++i) vc[i].clear();
}
return 0;
}
C++ 解法, 执行用时: 554ms, 内存消耗: 47992K, 提交时间: 2022-03-15 23:03:54
#include<bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
int T,n,a[100005],q;
struct que{
int l,r,id;
}A[100005];
int P[100005][35],Ln[100005],D[100005][35];
map<int,int> G;
map<int,ll> Gi;
vector<PII> F[100005];
int Pi[100005],di[100005];
ll L,R,S,X,Ans[100005],d[100005];
int ans[100005];
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
void print(ll x){
if(x>=10) print(x/10);
putchar(x%10+'0');
}
int cmp(que u,que v){
return u.r<v.r;
}
void add(int x,int y){
while(x<=n) d[x]+=y,x+=x&-x;
}
ll query(int x){
ll res=0;
while(x) res+=d[x],x-=x&-x;
return res;
}
int main(){
T=read();
for(int o=1;o<=T;o++){
G.clear();
Gi.clear();
n=read();
for(int i=1;i<=n;i++) F[i].clear();
for(int i=1;i<=n;i++) a[i]=read();
q=read();
for(int i=1;i<=q;i++) A[i].l=read(),A[i].r=read(),A[i].id=i;
sort(A+1,A+q+1,cmp);
Ln[n]=1,P[n][1]=n,D[n][1]=a[n];
for(int i=n-1;i>=1;i--){
Ln[i]=1,P[i][1]=i,D[i][1]=a[i];
for(int j=1,v;j<=Ln[i+1];j++){
v=__gcd(D[i+1][j],a[i]);
if(v!=D[i][Ln[i]]) Ln[i]++,P[i][Ln[i]]=P[i+1][j],D[i][Ln[i]]=v;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=Ln[i];j++) F[P[i][j]].push_back(mp(i,D[i][j]));
}
int las=0;
for(int i=1;i<=n;i++) d[i]=0;
for(int i=1;i<=q;i++){
for(int j=las+1,sz;j<=A[i].r;j++){
sz=F[j].size();
for(int k=0,v;k<sz;k++){
v=F[j][k].fi;
if(v!=j) G[Pi[v]]--,Gi[Pi[v]]-=v,add(v,-di[v]);
Pi[v]=F[j][k].se;
G[Pi[v]]++,Gi[Pi[v]]+=v,di[v]=j;
add(v,j);
}
}
ans[A[i].id]=Pi[A[i].l];
S=Gi[Pi[A[i].l]],X=G[Pi[A[i].l]];
L=(2ll*S/X+1-X)/2,R=L+X-1;
if(L<A[i].l) X-=(A[i].l-L),L=A[i].l;
Ans[A[i].id]=1ll*X*(A[i].r+1)-query(R)+query(L-1);
las=A[i].r;
}
printf("Case #%d:\n",o);
for(int i=1;i<=q;i++) print(ans[i]),putchar(' '),print(Ans[i]),puts("");
}
return 0;
}