Codeforces Round #846 (Div. 2)（B，E）
B
题目大意是给一个长度为n的数组，我们可以把这个数组分成k段（k>1),我们有一个值是每一段的和的gcd
\(gcd(sum[1],sum[2]+...+sum[k])\),我们需要的是这个值的最大是多少
对于分成k段，假设此时的\(gcd\)为\(x\)
如果\(k=4\),那么\(sum[1]=x*cnt1 ,sum[2]=x*cnt2,sum[3]=x*cnt3,sum[4]=x*cnt4\),那么我们可以知道，这四个和都是\(x\)的倍数，并且要想\(x\)变得更大，那么我们考虑把后面的几个数合并，和还是\(x\)的倍数
对于\(gcd\),我们知道对于这些个不同的数（均是\(x\)的倍数）把某些数合并，才有可能可以让这些数的\(gcd\)变大
\(gcd=__gcd(sum[1],sum[2]+sum[3]+sum[4])\)
\(gcd=__gcd(sum[1]+sum[2],sum[3]+sum[4])\)
所以，我们可以想到，不管怎么分，只有分成两份的时候才有可能是那个最大的值
具体代码如下
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int maxn=2e5+10;
#define int long long
int a[maxn],sum[maxn];
int n,t;
void solve()
{
cin>>n;
sum[0]=0;
int ans=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
if (i==1) ans=a[i];
else
{
ans=__gcd(ans,a[i]);
}
}
for (int i=1;i<n;i++)
{
ans=max(ans,__gcd(sum[i],sum[n]-sum[i]));
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
D
交互题，不会
E
这个题通过分析后可以这么理解
输出一个\(L\)和\(R\),我们需要知道这一段之间的数的\(gcd\)有多少个不同的数
对于\(1\)到\(x\),我们可以通过
$ a=L,b=2*L,gcd(a,b)=L$
$ a=L+1,b=2*(L+1),gcd(a,b)=L+1$
$ a=L+2,b=2*(L+2),gcd(a,b)=L+2$
\(......\)
$ a=L+x,b=2*(L+x),gcd(a,b)=L+x,b=R$
那么对于\(gcd>=L\)的数有多少个呢
我们可以看到，有\(x+1\)个，\(cnt=x+1=\lfloor \frac{R}{2}\rfloor-L+1\)
那么对于\(gcd<L\)的，我们可以构造一个\(d\),其中一个数是\(d*\lceil \frac{L}{d}\rceil\),另外一个数是\(d*(\lceil \frac{L}{d}\rceil+1)\)
对于这个\(\lceil \frac{L}{d}\rceil\),我们可以发现可以有很多个\(d\)，\(\lceil \frac{L}{d}\rceil\)都是一样的值，对于这些数，我们有一个范围，\([l,r]\)都是一个值
\(\lceil \frac{L}{l}\rceil\),所以，看到这儿是不是会想到整除分块了
什么是整除分块？
通过这个我们有得到以下公式
\[\begin{cases} k=\lceil \frac{L}{i}\rceil =\frac{L+i-1}{i}=\lfloor \frac{L-1}{i}\rfloor+1\\ r=min(\lfloor \frac{R}{K+1}\rfloor,max(i)),\quad rk\leq L-1 \end{cases} \tag{1} \]那么我们可以变化一下
\[\begin{cases} k=\lfloor \frac{L-1}{i}\rfloor\\ r=min(\lfloor \frac{R}{K+2}\rfloor,max(i)),\quad rk\leq L-1 \end{cases} \tag{1} \]但是\(r\)的范围还要让\(r(k+1)<=r\),得到\(r=min(r,\lfloor \frac{R}{K+2}\rfloor)\)
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
int L,R;
int t;
void solve()
{
cin>>L>>R;
int ans=max(0ll,R/2-L+1ll);
int l=1,r=0;
for (;l<L;l=r+1)
{
int k=(L-1)/l;
r=(L-1)/k;
int rr=min(r,R/(k+2));
ans+=max(0ll,rr-l+1);
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}