1.空间碰撞题解首先会发现这个题目是无法模拟的，因为数据范围太大，如果模拟每秒的运动会超时。然后还会发现运动轨迹有很多次反射，这样并不好，有没有办法可以让反射变成直线呢？我们只需要在每次博士撞到墙的时候，做一次对称，会发现博士的运动等价于：博士从零点按照运动方向出发，一直走直线，然后把初始的正方形不断复制，无限复制下去，如果博士遇到某个正方形的顶点，就说明博士可以出去了。对此可以列出下面两个式子：dx*t=k1*a;dy*t=k2*a;我们要求的是t的最小正整数解。对任何一个式子而言，因为t是未知数，k1是未知数，所以是形如ax=by这样的式子；对于这样的式子，x的最小正整数解为lcm(a,b...

A-广告位招租中 考虑枚举每个gcd的值num。对于每个num，它的倍数经过gcd都可能成为它，于是我们统计每个num的倍数存在多少个（预处理后复杂度），然后从num=m开始遍历一遍找最大的k就可以了。这里有一个坑点：即使num的倍数有k个，也不一定能够得到gcd==num，比如2的倍数有4,4,8 然而gcd只能到达4.所以我们还需要用log的复杂度维护每个num的当前实际值。总复杂度为 #include<bits/stdc++.h> using namespace std; const int N=2e5+10; int cnt[N],num[N],a[N]; int main...

https://www.nowcoder.com/discuss/621847416875081728?sourceSSR=users

A-广告位招租中 考虑枚举每个gcd的值num。对于每个num，它的倍数经过gcd都可能成为它，于是我们统计每个num的倍数存在多少个（预处理后复杂度），然后从num=m开始遍历一遍找最大的k就可以了。这里有一个坑点：即使num的倍数有k个，也不一定能够得到gcd==num，比如2的倍数有4,4,8 然而gcd只能到达4.所以我们还需要用log的复杂度维护每个num的当前实际值。总复杂度为 #include<bits/stdc++.h> using namespace std; const int N=2e5+10; int cnt[N],num[N],a[N]; int main...