题解归档 - cf2226B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2226B
• 本地来源：problems/cf2226B/idea.md
• 题目链接：https://codeforces.com/contest/2226/problem/B
• 原始标题：cf2226B - Everything Everywhere

思路

cf2226B - Everything Everywhere

pattern: gcd / range width restriction.

claim: if a good subarray has width d=max-min, then every element is divisible by d. Inside [min,max] there are only two possible multiples of d, namely min and max, because max-min=d. Since the array is a permutation, any good subarray must have length exactly 2.

For adjacent pair (x,y), with mn=min(x,y) and d=|x-y|, gcd(x,y)=gcd(mn,d)=d iff d divides mn.

check: count adjacent pairs satisfying mn % d == 0.

代码

来源：problems/cf2226B/solution.cpp

/* Author: likely
 * Time: 2026-06-27
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int>p(n);
        for(int &x:p) cin>>x;
        ll ans=0;
        for(int i=0;i+1<n;i++){
            int mn=min(p[i],p[i+1]);
            int d=abs(p[i]-p[i+1]);
            if(mn%d==0) ans++;
        }
        cout<<ans<<"\n";
    }
    return 0;
}