CM1-DAY1题目总结
前言
因为是第一节课，虽然比较简单，但是还是有思维难度的
1. CESE-1081
题意
给定长度为 $n$ 序列 $a$ ，求 $\underset{1 \leq i,j \leq n}\max { {\gcd(i,j)}}$
数据范围
$n \leq 2e5 , 1 \leq a_i \leq 1e6$
思路
Case 1
显然有暴力思路，复杂度是 $O(n^2)$ 的
for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) ans=max(ans,gcd(a[i],a[j]));
Case 2
用桶记录 $a_1 \sim a_n$ 中，每个数的每一个因子出现的次数
统计答案时，从大到小遍历桶，若 $t_i \geq 2$ ，则输出答案
复杂度是 $O(n\sqrt{V})$ 的，其中 $V= \sum_{i=1}^na_i$
for(int i=1,m=sqrt(a[i]);i<=n;++i,m=sqrt(a[i])) for(int j=1;j<=m;++j) if(!(a[i]%j)) ++t[j];
for(int i=MAX;i;--i) if(t[i]>1) {cout<<i;return 0;}
Case 3（正解）
考虑优化
发现可以使用 枚举倍数 的方法做到 $O(n \log n)$
最开始对于每一个 $a_i$ ，令 t[a[i]]++;
统计答案时，从大到小遍历桶，对于当前的 $i$ ，令 $cnt=\sum^{n}_{i \vert j}{t_j}$
若 $cnt \geq 2$ ，则输出答案
while(n--) x=read(),t[x]++;
for(int i=M-1,cnt=0;i;--i,cnt=0){for(int j=i;j<M && cnt<2;j+=i) cnt+=a[j];if(cnt>1){cout<<i;return 0;}
}
2. 洛谷P13388
题意
给定长度为 $n$ 序列 $a$ ，求使 $\gcd(a_1+y,a_2+y,\cdot\cdot\cdot,a_{n-1}+y,a_n+y)$ 最大的最小 $y$
数据范围
$2 \leq n \leq 1000,1 \leq a_i \leq 10^{50}$
思路
$\Large {需要高精度！！！}$
令 $ans_y=\gcd(a_1+y,a_2+y,\cdot\cdot\cdot,a_{n-1}+y,a_n+y)$
显然 $ans_y \vert (a_i-a_j)$ ，其中 $1 \leq i,j \leq n$
所以 $\max{ans_y}=\gcd(a_i-a_j)$ ，其中 $1 \leq i,j \leq n$
令 $gcd=\gcd(a_i-a_j)$ ，其中 $1 \leq i,j \leq n$
考虑求最小的 $y$
可得 $y\equiv-a_1(\mod gcd)$
同时，对于 $gcd$ 易证 $\underset{1 \leq i,j \leq n}\gcd(a_i-a_j)=\underset{1 \lt i \leq n}\gcd(a_{i}-a_{i-1})$
3. sgu-137
题意
给定 $n,k$ ，保证 $\gcd(n,k)=1$ ，求一个长度为 $n$ 的序列，所有元素的和为 $k$ ，且 循环同构
注：对于循环同构，一个序列 $S_1 S_2 S_3 \cdot\cdot\cdot S_n$ 如果满足新序列 $S_{1-1} S_2 S_3 \cdot\cdot\cdot S_{n+1}$能够通过旋转的操作(不是翻转)来得到旧的序列，那么这个序列就循环重构
数据范围
$2 \leq n \leq 1000,1 \leq k \leq 30000$
思路
一个序列 $S_0 S_1 S_2 \cdot\cdot\cdot S_{n-1}$ 向右 $t$ 次后变为 $S_tS_{t+1}S_{t+2}\cdot\cdot\cdot S_{t-1}$
根据对应关系，可得 $S_0=S_t,S_1=S_{t+1}$
所以若 $S_i=S_j$ 当且仅当 $i \equiv j (\mod k)$
可得 $S_t=S_{2t}=\cdot\cdot\cdot=S_{mt}$
所以先将每个位置都赋值为 $k \div n$ ，再枚举一个 $t$ ，最后将 $t$ 的倍数位加上 $1$ 即可
for(t=1;t<n;++t) if((n-1)==(k%n)*t%n) break;
for(int i=t;i!=n-1;i=(i+t)%n) f[i]=1;
f[n-1]=1;
for(int i=0;i<n;++i) cout<<k/n+f[i]<<' ';