CF1916B
分析
题目给出的是 \(x\) 的两个小于 \(x\) 的最大因子，首先考虑 \(a\) 不整除 \(b\) 的情况。既然 \(a\) 不整除 \(b\)，那么 \(a\times b\) 必定是 \(x\) 的倍数，但是此时 \(a,b\) 就不一定是最大的，所以需要除以一些东西，这个东西要尽可能大，又要保证除完之后 \(x\) 是 \(a,b\) 的倍数，所以自然想到结果是 \(\frac{a\times b}{\gcd(a,b)}\)，也就是 \(\operatorname{lcm}(a,b)\)。
下一步考虑 \(b\) 是 \(a\) 的倍数的情况。注意到 \(x\) 可以表示为 \(b\times k(k\in\mathbb{N}^+,k>1)\)，那么如果 \(k\) 比 \(a\) 大，\(a\) 就不是最大的了，除非 \(k=b\)，此时 \(x=b^2\)。如果 \(k\) 比 \(a\) 小，\(k\times a\) 就比 \(a\) 大，同理 \(k\times a=b\)，此时 \(x=\frac{b^2}{a}\)，显然此结果比上一个小，所以答案就是它。
AC Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
long long a,b;
cin>>a>>b;
if(b%a==0) cout<<b*b/a<<endl;
else cout<<a*b/__gcd(a,b)<<endl;
}
return 0;
}
CF1916C
分析
可能是本年最后一篇 tj 啦。
注意到数列和只有在 \(a_i+a_j\) 为奇数的时候才会 \(-1\)，否则是不变的，所以先手肯定会优先选择同奇偶性的，后手反之，每次选择以后多会获得一个偶数。既然先手想让后手输，那就要尽量保证序列中不存在异奇偶性的两数，但是每次操作后都会多出来一个偶数，所以她肯定会选择使用两个奇数，此时后手再用一奇一偶，这就是一轮，每完成一轮，数列和 \(-1\)，所以答案是 \(sum-\lfloor\frac{odd}{3}\rfloor\)（\(sum\) 是原数列和，\(odd\) 是原数列奇数个数），但是还不止，由于可能有无法凑成一轮的奇数，我们需要考虑 \(odd\) 模 \(3\) 余 \(1\) 的情况，此时先手没有办法去两个奇数，她就只能选偶数，后手就会再让数列和 \(-1\)，所以如果 \(odd\equiv1(\bmod3)\)，那么答案还要减一，就做完了。
AC Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[100010];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cout<<a[1]<<' ';
int odd=a[1]%2,sum=a[1];
for(int i=2;i<=n;i++)
{
odd+=a[i]%2;
sum+=a[i];
cout<<sum-(odd/3+(odd%3==1?1:0))<<' ';
}
cout<<endl;
}
signed main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}