Rinne Loves Sequence

Rinne Loves Sequence

https://ac.nowcoder.com/acm/problem/22599

Rinne Loves Sequence

思路

图片说明

写完后看了一下ac代码,果然就我的最暴力了。

代码

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 10;

int prime[N], mu[N], num[N], n, cnt;

bool st[N], vis[N];

vector<int> fac[N];

void init() {
    mu[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!st[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= cnt && 1ll * i * prime[j] < N; j++) {
            st[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i < N; i++) {
        for(int j = i; j < N; j += i) {
            fac[j].push_back(i);
        }
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    scanf("%d", &n);
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        int op, x;
        scanf("%d %d", &op, &x);
        if(op == 1) {
            if(vis[x]) continue;
            vis[x] = 1;
            for(auto d : fac[x]) {
                ans += mu[d] * num[d];
                num[d]++;
            }
        }
        else if(op == 2) {
            if(!vis[x]) continue;
            vis[x] = 0;
            for(auto d : fac[x]) {
                num[d]--;
                ans -= mu[d] * num[d];
            }
        }
        else {
            printf("%lld\n", ans);
        }
    }
    return 0;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像 头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-14 18:10
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
3 收藏 评论
分享

全站热榜

正在热议