C.差分维护，D.容斥原理 CodeTON Round 3 _生活百科

C. Complementary XOR题目大意：给你两个01串ab，问你是否可以通过一下两种操作在不超过n+5次的前提下将两个串都变为0，同时需要输出可以的操作方案

选择一个区间[l,r]
将串a的[l,r]翻转(0 $\rightarrow$ 1,1 $\rightarrow$0)，同时将b的[1,l)和（r,n]区间翻转

解题思路：通过写两组样例，我们可以尝试这种思路，因为我们需要输出可以的操作方案，我们很难去考虑同时操作a,b两个串的操作，所以我们尝试只考虑a串。将a串的全部0变成1，观察b串经过这种操作后的结果。我们可以发现，如果a串全为1，那b串此时有三种可能：

全为0
全为1
即含1，又含0

我们发现状况1可以通过对a进行一次[1,n]操作使a，b都为0状况2可以通过对a进行一次[1,1],[2,n]操作使a,b都为0（观察最后一个样例）但是状况3我们没有任何办法使得a，b都为0
自此整个题目分析完毕，我们只需要记录让a全部为1的操作对b的影响，最后看b串是否属于情况1,2即可
我们观察操作对b的影响是对[1,l)和（r,n]整个的影响，所以可以理解为对[1,l)和（r,n]操作次数都+1，因为翻转2次等于没翻转，（只有翻转奇数次才会真的翻转），因为是对整个区间+1，所以就可以考虑用差分维护（O(1)）
操作影响如下，假如选择的区间为[i,i],对b的影响就是b[1] += 1;b[i]-=1;b[i+1] += 1;
代码实现：

# include<iostream># include<bits/stdc++.h>using namespace std;# define int long long# define endl "\n"const int N = 2e5 + 10, inf = 1e9 + 7;int b[N];int a[N];void solve() {	int n;	cin>>n;	for(int i = 1;i <= n+1;++i) b[i] = a[i] = 0;	string s1,s2;	cin>>s1>>s2;	s1 = "?"+s1;	s2 = "?"+s2;	bool ok = true;	vector<pair<int,int>> ans;	for(int i = 1;i <= n;++i)//看看两个串是不是本身就为全0{if(s1[i]!= '0'||s2[i] != '0') {ok = false;break;}	}	if(ok){cout<<"YES"<<endl;cout<<0<<endl;return;	}	for(int i = 1;i <= n;++i){if(s1[i] == '0'){ans.push_back({i,i});b[1] += 1;//差分维护对b的影响b[i]-=1;b[i+1] += 1;}	}	for(int i = 1;i <= n;++i){a[i] = a[i-1]+b[i];//前缀和计算对每个位置的影响	}	for(int i = 1;i <= n;++i){if(a[i]&1){//如果操作次数为奇数则进行变化if(s2[i] == '0') s2[i] = '1';else s2[i] = '0';}	}	for(int i = 1;i <= n;++i){if(s2[i] != s2[1])//非（全0或者全1）{cout<<"NO"<<endl;return;}	}	if(s2[1] == '0'){ans.push_back({1,n});	}	else{ans.push_back({1,1});ans.push_back({2,n});	}	cout<<"YES"<<endl;	cout<<ans.size()<<endl;	for(auto [x,y]:ans){cout<<x<<" "<<y<<endl;	}}int tt;signed main() {	ios::sync_with_stdio(false);	cin.tie(0);	cout.tie(0);	tt = 1;	cin >> tt;	while (tt--)solve();	return 0;}

D. Count GCD题目大意：对于给定n,m，给你一个含n个数的数组，数组中每个数的取值范围在[1,m]
问能构造多少组数组b满足一下条件：

b[i] $\in$[1,m]
gcd(b[1],b[2],...,b[i]) = a[i]

解题思路：基本看到构造多少组b满足以上条件的就可以考虑原数组每一位的贡献了，类似于组合数学是每一位的贡献的积为总的组数所以总的框架就是

int ans = 1;	for(int i = 2;i <= n;++i){if(a[i] == a[i-1]){int t = m/a[i];//当前这一位的贡献ans = ans*t%mod;//总贡献}else{int t = cal(a[i-1]/a[i],m/a[i]);//当前这一位的贡献ans = ans*t%mod;}	}	cout<<ans<<endl;

【C.差分维护，D.容斥原理 CodeTON Round 3】然后考虑每一位的贡献是怎么样的形式我们写两组数据大概可以的到一下的思路：因为是前缀gcd，所以明显每个数的质因子是不断变小的，然后我们如果要求解b[i]就有如下思路：gcd(a[i-1],b[i]) = a[i]那我们要求的其实就是a[i]的倍数，比如a[i-1] = 6,a[i] = 3,那能够满足g(6,b[i]) = 3的只有3的倍数（3,6,9,12,15.....k*3<= m）,但是我们很容易就发现6,12是不能选的gcd(6,6||12) = 6 ，同理如果m/a[i] (所有的倍数)包含a[i-1]/a[i]的质因子的时候就都不能选
所以，问题可以转化为：从[1，m/a[i]]中选与（a[i-1]/a[i])互质的数有多少个
于是引入容斥原理：

文章插图
Tot = C$_n$$^1$ - C$_n$$^2$ + C$_n$$^3$.....
用韦恩图表示如下：

文章插图

文章插图
所以我们就考虑用总的（m/a[i])-res（所有与a[i-1]/a[i]不互质的数的并集）
之所以取与a[i-1]/a[i]不互质的数的并集是因为它比较好表示，用（m/a[i])/（选中的因子的积)就是不互质数的数量比如从1,2,3,4,5,6中求与2,3不互质的数实际上就是6-（2的倍数（{2,4,6} $\rightarrow$6/2 = 3）+3的倍数（{3,6} $\rightarrow$6/3 = 2）-（2*3）的倍数（{6} $\rightarrow$6/6 = 1）） = 6-3-2+1 = 2{1,5}