Zerojudge f586：數字D×D & f587：數字D×D 續 & f588：數字D×D 番外篇

Zerojudge f586 & f587 & f588

f586：數字D×D

題目大意：求莫比烏斯函數 $μ(n)$。

解法：直接求或用線性篩都可以。

$\text{Code：}$

直接

#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
int main() {
    ios::sync_with_stdio (false);
    cin.tie (0);
    int t, pr[168] = {2}, now = 1;
    for (int i = 3; i <= 1000; i++) {
        bool b = 1;
        for (int j = 0; j < now; j++)
            if (i % pr[j] == 0) {
                b = 0;
                break;
            }
        if (b)
            pr[now++] = i;
    }
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if (n == 1) {
            cout << "1\n";
            continue;
        }
        int prsum = 0;
        bool b = 0;
        for (int i = 0; i < 168; i++) {
            int even = 0;
            if (n == 1)
                break;
            while (n % pr[i] == 0)
                n /= pr[i], even++;
            prsum += (even != 0);
            if (even > 1) {
                b = 1;
                break;
            }
        }
        if (b) {
            cout << "0\n";
            continue;
        }
        if (n != 1)
            prsum++;
        if (prsum % 2)
            cout << "-1\n";
        else
            cout << "1\n";
    }
}

預處理

#pragma GCC optimize("O3")
#include <stdio.h>
#include <bitset>

#define GU getchar_unlocked()
#define PU putchar_unlocked
#define LL long long

int in() {
    int re = 0;
    char c = GU;
    while (c == ' ' || c == '\n')
        c = GU;
    while (c >= '0' && c <= '9')
        re = (re << 3) + (re << 1) + c - '0', c = GU;
    return re;
}

void out (LL x) {
    char str[20];
    int pos = 0;
    do {
        str[pos++] = x % 10 + '0';
        x /= 10;
    } while (x);
    for (int i = pos - 1; i >= 0; i--)
        PU (str[i]);
    PU ('\n');
}

int get_syl (bool lok, bool mob) {
    if (lok)
        return -1;
    return mob;
}

const int MAX = 1000000;
const int PSIZE = 499;

std::bitset < MAX + 5 > bs;
std::bitset < MAX + 5 > loki;
std::bitset < MAX + 5 > mmm;
int p[PSIZE + 5];

void init() {
    int pos = 0;
    mmm[1] = 1;
    for (int i = 2; i <= MAX; i++) {
        if (!bs[i]) {
            loki[i] = 1;
            if (pos < PSIZE)
                p[pos++] = i;
        }
        for (int j = 0; j <= pos; j++) {
            int now = i * p[j];
            if (now > MAX)
                break;
            bs[now] = 1;
            if (i % p[j] == 0)
                break;
            if (loki[i])
                mmm[now] = 1;
            else if (mmm[i])
                loki[now] = 1;
        }
    }
}

void solve() {
    int n = in(), ans = get_syl (loki[n], mmm[n]);
    if (ans == -1)
        PU ('-'), PU ('1');
    else if (ans == 1)
        PU ('1');
    else
        PU ('0');
    PU ('\n');
}

int main() {
    init();
    int t = in();
    while (t--)
        solve();
}

f587：數字D×D 續

題目大意：求 $μ(1) +...+ μ(n)$。

解法：杜教篩。

#pragma GCC optimize("O3")
#include <stdio.h>
#include <bitset>
#include <map>

#define GU getchar_unlocked()
#define PU putchar_unlocked

int in() {
    int re = 0;
    char c = GU;
    while (c == ' ' || c == '\n')
        c = GU;
    while (c >= '0' && c <= '9')
        re = (re << 3) + (re << 1) + c - '0', c = GU;
    return re;
}

void out (int x) {
    char str[15];
    int pos = 0;
    if (x < 0)
        PU ('-'), x = -x;
    do {
        str[pos++] = x % 10 + '0';
        x /= 10;
    } while (x);
    for (int i = pos - 1; i >= 0; i--)
        PU (str[i]);
    PU ('\n');
}

const int MAX = 1664510;
const int PSIZE = 209;

std::bitset < MAX + 5 > bs;
short mm[MAX + 5] = {}, p[PSIZE + 5];
std::map<int, int> um;

void mm_seive() {
    mm[1] = 1;
    for (int i = 2, pos = 0; i <= MAX; i++) {
        if (!bs[i]) {
            mm[i] = -1;
            if (pos < PSIZE)
                p[pos++] = i;
        }
        for (int j = 0, now = i * p[0]; j < pos && now <= MAX; j++, now = i * (j < pos ? p[j] : 0)) {
            bs[now] = 1;
            if (i % p[j] == 0)
                break;
            mm[now] = -mm[i];
        }
    }
    for (int i = 1; i <= MAX; i++)
        mm[i] += mm[i - 1];
}

int get_sumob (int x) {
    if (x <= MAX)
        return mm[x];
    if (um[x])
        return um[x];
    int re = 1;
    for (int i = 2, j, k; i <= x; i = j + 1) {
        ...
        re -= get_sumob (k) * (j - i + 1);
    }
    return um[x] = re;
}

void solve() {
    int n = in();
    out (get_sumob (n));
}

int main() {
    mm_seive();
    int tt = in();
    while (tt--)
        solve();
}

f588：數字D×D 番外篇

題目大意：求歐拉函數 $φ(1) +...+ φ(n)$。

解法：也是杜教篩。

#pragma GCC optimize("O3")
#include <stdio.h>
#include <bitset>
#include <unordered_map>

#define GU getchar_unlocked()
#define PU putchar_unlocked
#define LL long long

int in() {
    int re = 0;
    char c = GU;
    while (c == ' ' || c == '\n')
        c = GU;
    while (c >= '0' && c <= '9')
        re = (re << 3) + (re << 1) + c - '0', c = GU;
    return re;
}

void out (LL x) {
    char str[20];
    int pos = 0;
    if (x < 0)
        PU ('-'), x = -x;
    do {
        str[pos++] = x % 10 + '0';
        x /= 10;
    } while (x);
    for (int i = pos - 1; i >= 0; i--)
        PU (str[i]);
    PU ('\n');
}

const int MAX = 1664510;
const int PSIZE = 209;

std::bitset < MAX + 5 > bs;
short mm[MAX + 5] = {}, p[PSIZE + 5];
std::unordered_map<int, int> um;

void mm_seive() {
    mm[1] = 1;
    for (int i = 2, pos = 0; i <= MAX; i++) {
        if (!bs[i]) {
            mm[i] = -1;
            if (pos < PSIZE)
                p[pos++] = i;
        }
        for (int j = 0, now = i * p[0]; j < pos && now <= MAX; j++, now = i * (j < pos ? p[j] : 0)) {
            bs[now] = 1;
            if (i % p[j] == 0)
                break;
            mm[now] = -mm[i];
        }
    }
    for (int i = 1; i <= MAX; i++)
        mm[i] += mm[i - 1];
}

int get_sumob (int x) {
    if (x <= MAX)
        return mm[x];
    if (um[x])
        return um[x];
    int re = 1;
    for (int i = 2, j, k; i <= x; i = j + 1) {
        ...
        re -= get_sumob (k) * (j - i + 1);
    }
    return um[x] = re;
}

LL get_sumora (int x) {
    LL re = 0;
    for (int i = 1, j, k; i <= x; i = j + 1) {
        ...
        re += (LL) (...) * k * k;
    }
    return ((re-1) >> 1) + 1;
}

void solve() {
    int n = in();
    out (get_sumora (n));
}

int main() {
    mm_seive();
    int tt = in();
    while (tt--)
        solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！