牛客 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;

}

巴特西

牛客 2020.10.20 TG 前两题

T1 GCD

T2 包含

最新文章

热门文章