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;
}