2023牛客暑期多校训练营6

G-Gcd

题意：一开始给你一个集合\(S = \lbrace x,y \rbrace(x\neq y)\)。然后你可以执行以下两个操作：

1.从\(S\)中选择两个元素\(a,b(a \neq b )\)，把\(a-b\)加入集合。
2.从\(S\)选择2个元素是\(a,b(a \neq b )\),把\(gcd(|a|,|b|)\)加入集合里面。

特别的，\(\gcd(a,0) = \gcd(0,a) = a\)

你的任务是通过以上操作，使得\(z\)在集合里面。如果可能回答\(YES\),否则\(NO\)。

思路：

首先对\(z = 0\)特判：如果\(z = 0\)且\(x,y\)其中一个等于\(0\)，输出\(YES\),否则\(NO\)。
对\(x,y\)辗转相减法，我们只能得到其\(\gcd\)的若干倍。

对于2的证明：

设\(g = \gcd(x,y),x = ag,y = bg\)

\(x-g = (a-1)g\)

\(x-g-g = (a-2)g\)

以此类推我们可以得到\(2g\)

\(g-2g= -g\)

\(g-(-g) = 2g\)

\(g-(-g)-(-g) = 3g\)

以此类推我们可以得到任意\(g\)的倍数。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+10;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ll x,y,z;
		cin>>x>>y>>z;
		ll g = __gcd(x,y);
		if(z==0)
		{
			if(x==0||y==0)
				cout<<"YES\n";
			else cout<<"NO\n";
		}
		else{
			if(z%g==0)cout<<"YES\n";
			else cout<<"NO\n";
		}
	}
	return 0;
}

E-Sequence

题意：给你一个\(n\)个元素的集合从\(a_1,a_2..a_n\)。

对于每个询问，给你\(l,r,k\),问你，你能不能找到一个数组\(b\)满足：

\(l\le b_1<b_2<b_3<...<b_{k-2}<r\)
\(sum(l,b_1),sum(b_1+1,b_2),...,sum(b_{k-1}+1,r)\)都是\(2\)的倍数。

特别的，当\(k = 1\)时，它应该满足\(sum(l,r)\)是\(2\)的倍数。

\(sum(l,r) =\sum_{i = l}^{r}a_i(l\le r)\)

如果能找到输出\(YES\),否则输出\(NO\)。

思路：题意用人话来说呢就是，给你一段区间\([l,r]\)，问你能不能把它切成\(k\)段，每段的和都是偶数。

对于\([1,n]\)区间，我们可以先预处理出前缀可以分出的最大段数。我们考虑什么时候能分成一段？当它是偶数的时候肯定是可以的。但是我们需要处理当我们碰到奇数怎么办呢？我们需要奇数的个数是偶数才行，我们可以把它想象成括号。什么意思呢？当我们碰到第一个奇数时候，以它作为左括号，什么时候是右括号？就是碰到下一个奇数的时候，而两者之间的偶数我们不用管，也不能算入段中，因为如果要合法的话，这两个奇数+中间的偶数必然在一段里面。由此进行\(dp\)，前缀统计贡献。

但是这个时候我们又遇到了一个问题，因为我们查询的是区间，而预处理的时候，我们只处理了把奇数个奇数处理为左括号，但是我们的询问中，不一定是这样，所以我们还需要处理出以偶数个奇数处理为左括号的情况。这样的话，判断的时候，我们先判断当前区间的第一个奇数是奇数个奇数还是偶数个奇数，再进行判断即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+10;
ll odd[N],f[N],g[N],sum[N];
ll a[N];

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n,q;
		cin>>n>>q;
		for(int i = 1;i<=n;i++)
			odd[i] = 0,f[i] = 0 ,g[i] = 0,sum[i] = 0;
		for(int i = 1;i<=n;i++)
		{
			cin>>a[i];
			odd[i] = odd[i-1]+(a[i]%2!=0);//统计前缀奇数个数
			sum[i] = sum[i-1]+a[i];//前缀和
		}
		ll tmp = 0;
        //f数组处理奇数个奇数是左括号情况
		for(int i = 1;i<=n;i++)
		{
			f[i] = f[i-1];
			tmp+=a[i];
            //如果是偶数，直接作为一段，如果碰到的是奇数，中间碰到的偶数不算，直到碰到下一个奇数
			if(tmp%2==0)
				f[i]++,tmp = 0;
		}

		bool ok = false;
		tmp = 0;
        //g数组处理偶数个奇数是左括号情况
		for(int i = 1;i<=n;i++)
		{
			g[i] = g[i-1];
			tmp += a[i];

			if(a[i]%2==0&&!ok)g[i]++;//一开始的偶数
			if(a[i]%2 && !ok)ok = true,tmp = 0;//第一个奇数我们是不算的

			if(tmp%2==0&&ok)
			{
				g[i]++;
				tmp = 0;
			}
		}
		while(q--)
		{
			int l,r,k;
			cin>>l>>r>>k;
			ll t = odd[l-1]+1;//odd[l-1]看l前面有多少个奇数，再+1就是前奇数的位置
			if((t%2)&&((f[r]-f[l-1])>=k)&&((sum[r]-sum[l-1])%2==0))
			{
				cout<<"YES\n";
			}
			else if(!(t%2)&&((g[r]-g[l-1])>=k)&&((sum[r]-sum[l-1])%2==0))
			{
				cout<<"YES\n";
			}
			else cout<<"NO\n";
		}
	}
	return 0;
}

C-idol!!

题意：\(n\)属于\(1e18\)，让你求\(1!!*2!!*...*n!!\)的末尾有多少个连续\(0\)。

思路：一开始我是想要把双阶乘转化为单阶乘然后去写的，然后打表发现是等差，然后开始推柿子，中间可能哪里推挂了，写了好久没写出来TAT。

重新整理下思路，这题的正解也确实是等差数列。具体是怎么做的呢？

我们考虑甚么对末尾的\(0\)有贡献？是数中\(2\)因子的数量和\(5\)因子的数量，\(0\)的数量=\(\min(cnt2,cnt5)\)，但是我们发现\(2\)的数量是很多的，那么问题转化为考虑\(5\)的贡献。

对于\(n\)为奇数时：\(n!! = 1*3*5*...n。\)

那么能产生贡献的数是\(5,15,25,35,55...\)

特别地，当数值为\(25,125...\)这些属于\(5^k\)的，它们的贡献有多个\(5\)的，所以我们的外层循环枚举\(5^k\)，这样\(25,125...\)的贡献就又会被算到，做到不遗漏。

那么对于\(base = 5\)的时候：\(5\)能产生的贡献是，在\(n\)以内，\(5\)以及\(5\)后面所有的奇数(因为它们双阶乘包含了\(5\),个数是\(\dfrac{n-5}{2}+1\))。同样对于\(15\)的话就是，在\(n\)以内，\(15\)能产生的贡献是\(15\)以及\(15\)后面的所有奇数\(\dfrac{n-15}{2}+1\)。

所以对于\(base = 5\)时候的贡献就是：\((\dfrac{n-5}{2}+1)+(\dfrac{n-15}{2}+1)+(\dfrac{n-25}{2}+1)+...\)

化简一下就是：\((\dfrac{(n-5)+(n-15)+(n-15)+...}{2})+(1+1+...+1)\)

我们发现，对于前面那项的分子部分\((n-5)+(n-15)+(n-15)+...\)是一个等差数列：以\((n-5)\)为首项，\(-10\)为公差,有\(\dfrac{n-5}{10}+1\)项数的等差。而对于后面那部分的贡献就是项数\(*1\),两部分加起来就是\(base = 5\)时候的总贡献，即：\({\dfrac{((n-5)+((n-5)+(\dfrac{n-5}{2}+1-1)*(-10))*(\dfrac{n-5}{10}+1)}{2}}+(\dfrac{n-5}{10}+1)\)。

对于\(base = 5\)的情况我们讨论完了，那通式就是：

\({\dfrac{((n-base)+((n-base)+(\dfrac{n-base}{2}+1-1)*(-2*base))*(\dfrac{n-base}{2*base}+1)}{2}}+(\dfrac{n-base}{2*base}+1)\)

用函数\(calc\)来计算数列答案就是\(calc(n-base,-2*base,(n-base)/(2*base)+1)\)

那么综上所述，奇数项的贡献就是\(calc(n-base,-2*base,(n-base)/(2*base)+1)/2+((n-base)/(2*base)+1)\)。

那么接下来就是偶数的情况。

对于\(n\)为偶数时候:\(n!! = 2*4*6*...\)

那么能产生贡献的数是\(10,20,30,...\)

和奇数类似的\(50 = 25*2 = 5^2*2\)也是有多个贡献的，和奇数处理方法一样，加一个外层循环。

以\(base = 5\)为例：\((\dfrac{n-10}{2}+1)+(\dfrac{n-20}{2}+1)+(\dfrac{n-30}{2}+1)+...\)

化简一下就是：\((\dfrac{(n-10)+(n-20)+(n-30)+...}{2})+(1+1+...+1)\)

我们发现，对于前面那项的分子部分\((n-10)+(n-20)+(n-30)+...\)是一个等差数列：以\((n-10)\)为首项，\(-10\)为公差,有\(\dfrac{n}{10}\)项数的等差。而对于后面那部分的贡献就是项数\(*1\),两部分加起来就是\(base = 5\)时候的总贡献，即：\({\dfrac{((n-10)+((n-10)+(\dfrac{n-10}{10}+1)*(-10))*(\dfrac{n}{10})}{2}}+(\dfrac{n-10}{10}+1) = {\dfrac{((n-10)+((n-10)+(\dfrac{n}{10})*(-10))*(\dfrac{n}{10})}{2}}+(\dfrac{n}{10})\)。

对于\(base = 5\)的情况我们讨论完了，那通式就是：

\({\dfrac{((n-base*2)+((n-base*2)+(\dfrac{n}{base*2})*(-base*2))*(\dfrac{n}{base*2})}{2}}+(\dfrac{n}{base*2})\)

用函数\(calc\)来计算数列答案就是\(calc(n-base*2,-base*2,n/(base*2))\)

那么综上所述，偶数项的贡献就是\(calc(n-base*2,-base*2,n/(base*2))/2+(n/(base*2))\)。

需要注意的点：

开__int128
开始时，如果\(n\)是偶数，那处理奇数项的情况\(n = n-1\),同理\(n\)的奇数，处理\(n\)为偶数的时候令\(n = n-1\)。使得它的范围是\(n\)以内最大可以满足条件的数。

#include<bits/stdc++.h>
using namespace std;
inline __int128 rd(){__int128 x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline void pt(__int128 x){if (x < 0){putchar('-');x = -x;}if (x > 9) pt(x / 10);putchar(x % 10 + '0');}

__int128 calc(__int128 a1,__int128 d,__int128 n)
{
	return (a1+(a1+(n-1)*d))*n/2;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	__int128 n,t;
	n = rd();
	__int128 ans1 = 0,ans2 = 0;	
	if(n%2==0)
		t = n-1;
	else t = n;
	for(__int128 base = 5;base<=t;base*=5)
		ans1 += calc(t-base,base*(-2),(n-base)/(base*2)+1)/2+(n-base)/(base*2)+1;
	
	if(n%2)
		t = n-1;
	else t = n;
	for(__int128 base = 5;2*base<=t;base*=5)
		ans2 += calc(t-base*2,base*(-2),n/(base*2))/2+(n/(base*2));
	
	pt(ans1+ans2);
	return 0;
}