牛客 2020.10.20 TG 前两题

T1 GCD

数学水题。。。

对于每个数，如果这个数有两个及以上的质因数的话，它所有除 $1$ 之外的因数求 $GCD$ 的值一定为 $1$。那么判断是否是质数或质数的次方即可（质数除 $1$ 之外的因数只有它本身，而质数的次方除 $1$ 之外的质因数只有一个，故不存在两个及以上的质因数。

再来考虑特殊的是质数的次方 $x^n$ 的情况，它除 $1$ 之外的因数一定只有 $x$，所以得出这个质数并累加答案即可。那就跑欧拉筛的时候边跑边暴力更新呗。

#include <cstdio> #include <cmath> const int MAXN = 1e7 + 5; int num[MAXN], len = 0; bool flag[MAXN]; int vis[MAXN]; typedef long long LL; void euler(int n) { // 欧拉筛 for(int i = 2; i <= n; i++) { if(!flag[i]) { num[++len] = i; int t = 1; while((LL)t * i <= n) { // 暴力枚举次方 t *= i; vis[t] = i; // 记录这个次方对应的质数 flag[t] = true; } } for(int j = 1; j <= len; j++) { if(i * num[j] > n) break; flag[i * num[j]] = true; if(i % num[j] == 0) break; } } return ; } int main() { int m, n; scanf ("%d %d", &m, &n); euler(n); LL ans = 0; flag[1] = true; for(int i = m; i <= n; i++) { if(i == 1) // 排除1的情况 continue; if(!flag[i]) // 是质数 ans += i; // （所有除1之外的因数的GCD即是本身 else if(vis[i]) // 如果是质数的某个次方 ans += vis[i]; // 加上那个对应的质数 else // 否则这个数有两个及以上的质因子，加一即可 ans++; } printf("%lld\n", ans); return 0; }

T2 包含

显然如果用n方的算法会卡到飞起。。。（右边巨佬考场 DFS 记忆化过掉了呢

考虑优化。我们在每一次输入的时候更新一下有哪些数 $\&$ 上这个数等于内个数本身。记这个集合内的数为 $Q$，即是寻找有哪些 $X$ 满足 $Q\&X=X$。

对于一个 $Q\&X=X$，在二进制数位中 $X$ 等于 $1$ 的位，对应的 $Q$ 中的位一定等于 $1$，但因为 $Q$ 是确定的，所以我们考虑依次替换掉 $Q$ 二进制当中等于 $1$ 的位，将其改为 $0$，枚举所有情况即是找到了所有的 $X$。

至于如何枚举 $Q$ 中为 $1$ 的位……芜湖起飞。

int t = x; while(t) { vis[t] = true; t = (t - 1) & x; }

就是上述代码，最好在草稿纸上手推一下，不然很难理解。

为此我还和JC讨论了好久。

结论：上述代码按以下顺序枚举为 $1$ 的位改其为 $0$。

Q: 1 0 0 0 1 0 0 1 1. ^ 2. ^ 3. ^ ^ 4. ^ 5. ^ ^ 6. ^ ^ 7. ^ ^ ^ #include <cstdio> const int MAXN = 1000005; bool vis[MAXN]; int main() { int n, m; scanf ("%d %d", &n, &m); for(int i = 1; i <= n; i++) { int x; scanf ("%d", &x); if(vis[x]) continue; int t = x; while(t) { vis[t] = true; t = (t - 1) & x; } } while(m--) { int x; scanf ("%d", &x); if(vis[x]) printf("yes\n"); else printf("no\n"); } return 0; }