codeforces 1424J, чтобы пройти этот вопрос, я использовал весь родовой C++!

Привет всем, мы выбрали вопрос J игры Bubble Cup Div2, не спрашивайте меня, что такое Bubble Cup, я не знаю. В общем, это алгоритмическое соревнование. Возможно, популярность этого конкурса относительно низкая, а количество участников не очень велико.В качестве сегодняшнего вопроса мы выбрали вопрос J с умеренным количеством прохожих.

Ссылка на сайт:codeforces.com/contest/142…

Этот вопрос очень хороший, онкачественные математические задачи, также соответствует моему аппетиту. Потому что трюков не так уж и много, у некоторых только столкновение мышления и логики.

смысл названия

Все мы знаем, что для двух чисел a и b можно легко найти их наибольший общий делитель. $\gcd(a, b)$ . Предположим, что наибольший общий делитель чисел a и b равен k, если $k, \frac{a}{k}, \frac{b}{k}$ Длина этих трех чисел может образовывать правильный треугольник, тогда мы считаем, что a и b дружественны друг другу.

Для правового треугольника мы предполагаем, что три его стороны равны a, b и c соответственно, и должно быть a + b > c, a + c > b, b + c > a, т. е.Сумма любых двух сторон больше третьей стороны. Это должно быть содержанием начальной школы математики, и все должны быть знакомы с ней.

Если номер не может найти дружественный номер в наборе, он считается одиноким. Теперь нам дан ряд n, представляющий набор натуральных чисел от 1 до n, и мы запрашиваем количество одиноких чисел в этом наборе.

Образец

Во-первых, учитывая t ( $1\leq t \leq 10^6$ ), представляющий количество тестовых данных.

Затем дана строка из t целых чисел, представляющих различные n ( $1\leq n \le 10^6$ ). Для каждого n выведите целое число, представляющее количество одиноких чисел в множестве натуральных чисел 1-n.

Когда n=5, одинокие числа равны 1, 3 и 5 соответственно. Когда n=10, одинокими числами являются 1, 5 и 7.

отвечать

Поскольку диапазон n равен 1e6, невозможно принять $O(n^2)$ алгоритм, поэтому мыНевозможно перечислить все комбинации двух чисел. Следовательно, насильственное решение невозможно, мы должны проанализировать проблему и сделать другие выводы, чтобы упростить проблему.

Во-первых, мы можем легко найти, что1 должно быть одиноко. Причина также проста, для любого натурального числа х наибольший общий делитель его и 1 равен 1. Тогда результат равен 1, 1 и х. Поскольку x не может повторяться с 1, минимальное значение x равно 2, но даже если оно равно 2, оно не удовлетворяет 1+1>2, поэтому треугольник не должен образовываться. Итак, независимо от того, что такое n, 1 должно быть одиноким.

Другой момент, о котором легче думать, — это случай взаимно простого числа, предполагая, что числа a и b взаимно просты, то есть их наибольший общий делитель равен 1. Три стороны треугольника, которые мы получаем, равны 1, а, b. Точно так же a и b не равны, поэтому a и b отличаются как минимум на 1, поэтому они не могут образовывать три стороны треугольника. такЕсли два числа взаимно просты, они не должны быть дружественными. Если оглянуться назад с этого момента, то причина одиночества 1 именно в том, что она относительно проста по отношению ко всем другим числам.

Что мы можем ожидать от этого?

Кстати, на ум приходят простые числа.Наибольший общий делитель простого числа и всех остальных натуральных чисел равен либо 1, либо самому себе. Мы уже разобрали случай, когда наибольший общий делитель равен 1. Давайте проанализируем ситуацию, когда наибольший общий делитель равен ему самому. Мы предполагаем, что это простое число равно х, а другое число равно Ь. Поскольку наибольший общий делитель х и Ь равен х, это означает, что Ь кратно х. Тогда обозначим b как kx.

Таким образом, мы получаем три стороны треугольника, равные x, 1 и k соответственно. Мы можем получить три ограничения:

$x + 1 > k\to x > k-1$
$k + 1 > x$
$k + x > 1$

Третий пункт очевиден, на него можно не обращать внимания, давайте подробнее рассмотрим первые два. Мы можем объединить их, чтобы получить: $k + 1 > x > k-1$ , то существует только одно значение x, равное $x = k$ . Так есть ли предел k? k также ограничено, k не может принимать никаких значений, нам нужно убедиться, что $kx \leq n$ , это, $x \le \frac{n}{x}$ ,Сейчас $x \leq \sqrt{n}$ .

Проведя такую серию анализов, мы пришли к выводу, что для простого числа x, если оно хочет быть одиноким, оно должно удовлетворять $x \leq \sqrt{n}$ . И наоборот, его также можно получить, когда $x > \sqrt{n}$ Когда x — простое число, x должен быть одиноким.

Теперь мы закончили говорить о случае простых чисел, но мы не знаем о случае составных чисел, тогдаСуществуют ли составные числа, которые также являются одинокими?? На самом деле нет, мы можем доказать это таким образом. Будем считать, что речь идет о составном числе m, так как это составное число, оно должно уметь разлагать простые множители. и он должен быть разложен на меньше, чем $\sqrt{n}$ Первичный фактор , процесс доказательства также очень прост, потому чтоСоставные числа либо являются квадратами, либо имеют по крайней мере два простых делителя.. В любом случае, пока его главный множитель больше или равен $\sqrt{n}$ , то оно само должно быть больше n. Итак, это противоречие.

Поскольку составные числа должны быть в состоянии найти меньше, чем $\sqrt{n}$ Простой множитель , мы могли бы также предположить, что простым множителем является x, а составное число m записывается как ax. Диапазон a должен быть $[2, \frac{n}{x}]$ . Тогда все, что нам нужно сделать, это найти число b такое, что bx может быть дружелюбным к ax, и $bx \le n$ , а a и b взаимно просты, иначе не выполняется $\gcd(ax, bx) = x$ .

Так можно ли найти такое б? Конечно, можно, и это очень, очень просто. Давайте сначала проанализируем условия, которых мы хотим достичь.Поскольку мы хотим сделать треугольник законным, нам нужно выполнить 4 условия:

$x + a > b$
$x + b > a$
$a + b > x$
$\gcd(a, b) = 1$

С первыми двумя условиями мы можем получить диапазон b $a-x < b < a+ x$ . А как же последние два условия? На самом деле это очень просто, мы можем обсудить это по ситуации, если $a > x$ , то мы можем выбрать b = a-1, такое, что b должно удовлетворять условию. Если a

Таким образом, мы доказали, что,Все составные числа не должны быть одиночными, все они могут найти свои дружественные номера.

Итак, в конце концов, то, о чем мы просим, больше, чем $\sqrt{n}$ Количество простых чисел , но не забудьте добавить 1, потому что 1 также одиночное число, которое удовлетворяет условию. Так как n является наибольшим $10^6$ , если мы найдем простые числа одно за другим, то определенно будет слишком поздно, здесь мы можем использовать то, что мы ввели ранееМетод египетского ситачтобы быстро найти все простые числа.

Другой вопрос: что нам делать, если мы запрашиваем количество простых чисел в определенном диапазоне? На самом деле это очень просто, нам просто нужно использовать сумму префикса.

Вдобавок к этому в этом вопросе есть подводный камень, заключающийся в том, что времени очень мало. так что тот же алгоритмРеализация Python будет тайм-аут, В отчаянии мне пришлось использовать наследственный C++, чтобы переписать его снова, и, наконец, я прошел. Вы можете сравнить разницу в эффективности между Python и C++, которая весьма впечатляет.

Наконец, прикрепите код:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
// 一些宏定义
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>=b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
using namespace std;
const int N=1000050;
const long long Mod=1000000007;
int t, query[N];
int isprime[N], primecnt[N];


// 埃式筛法
void eratosthenes() {
    rep(i, 0, N) isprime[i] = 1;
    rep(i, 2, N) {
        if (isprime[i]) {
            for (int j = i+i; j < N; j += i) {
                isprime[j] = 0;
            }
        }
    }
    // 维护质数的前缀和
    rep(i, 2, N) {
        primecnt[i] = primecnt[i-1] + isprime[i];
    }
}


int main() {
    eratosthenes();
    scanf("%d", &t);
    rep(i, 0, t) {
        int query;
        scanf("%d", &query);
        printf("%d\n", primecnt[query] - primecnt[int(sqrt(query))] + 1);
    }
    return 0;
}

Вот и все, что касается сегодняшней статьи, и я искренне желаю вам удачи каждый день. Если вам все еще нравится сегодняшний контент, пожалуйста, зайдите на одинТройная поддержкабар~(Нравится, подписывайтесь, делайте репост)

Оригинальная ссылка, обратите внимание