[PYTHON] Comment calculer la quantité de calcul appris de ABC134-D

problème

https://atcoder.jp/contests/abc134/tasks/abc134_d

a été difficile. Ou plutôt, il était difficile de lire l'énoncé du problème.

Cette leçon

  1. Entier arbitraire = nuance comme tous les entiers
  2. Uniquement confirmé en résolvant dans l'ordre de l'arrière
  3. O(\sum(N/i)) = O(NlogN)

Comment calculer le montant du calcul

Question posée: Est-ce que $ O (\ sum (N / i)) $ est dans le temps?

Dans ce problème, il est nécessaire de trouver $ N / i $ à n'importe quel i. En considérant cela, il est bon d'effectuer l'intégration. Puisque $ \ int (1 / N) = logN $, il peut être supprimé par logN au pire.

Résumé

  1. Devenir une phrase mathématique
  2. Il est courant de juger la séquence de l'avant ou de l'arrière et il faut en être conscient.
  3. ** Compte tenu de l'intégration, le temps de calcul peut être obtenu à partir de la zone. ** **

code

N = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
b = [0] * N
M = 0
for i in range(N, 0, -1):
    ball = 0
    for j in range(i + i, N + 1, i):
        ball ^= b[j - 1]
    b[i - 1] = ball ^ a[i]
M = sum(b)
print(M)
for i in range(N):
    if b[i]:
        print(i + 1, end = ' ')

Recommended Posts

Comment calculer la quantité de calcul appris de ABC134-D
Comment calculer le coefficient d'autocorrélation
Comment trouver la quantité moyenne d'informations (entropie) de la distribution de probabilité d'origine à partir de l'échantillon
Comment vérifier la version de Django
Comment calculer Utiliser% de la commande df
Comment faire fonctionner Linux depuis la console
Comment accéder à la banque de données de l'extérieur
De l'introduction de l'API GoogleCloudPlatform Natural Language à son utilisation
Comment trouver la zone du diagramme de Boronoi
Modifiez le point décimal de la journalisation de, à.
Comment faire fonctionner Linux depuis l'extérieur Procédure
Comment mesurer la vitesse de la ligne depuis le terminal
De l'introduction de pyethapp à l'exécution du contrat
Histoire de passer de Pipenv à la poésie
[Numpy, scipy] Comment calculer la racine carrée d'une matrice Elmeet à valeur semi-régulière
[Python] Comment supprimer les valeurs en double de la liste
Comment connaître le numéro de port du service xinetd
Le mur lors du passage du service Django de Python 2.7 à la série Python 3
Calculer le volume à partir de la structure bidimensionnelle d'un composé
Comment obtenir le nombre de chiffres en Python
Calcul du nombre minimum de voix requis à partir du taux de vote
Comment résoudre la fonction récursive qui a résolu abc115-D
L'idée de Tensorflow a appris de la fabrication de pommes de terre
Comment lancer instantanément Jupyter Notebook à partir du terminal
Étapes pour calculer la probabilité d'une distribution normale
[Blender] Comment définir dynamiquement les sélections EnumProperty
[Python] Résumé de la façon de spécifier la couleur de la figure
Comment utiliser le modèle appris dans Lobe en Python
Comment frapper le document de Magic Function (Line Magic)
Comment accéder à la variable globale du module importé
Comment publier un ticket depuis l'API Shogun
[Selenium] Comment spécifier le chemin relatif de chromedriver?
[Python] Méthode de calcul de la formule d'approximation de la même section 0 qu'Excel [scikit-learn] Mémo
Résumé du début au chapitre 1 de l'introduction aux modèles de conception appris en langage Java
Comment augmenter la vitesse de traitement de l'acquisition de la position des sommets
[Ubuntu] Comment supprimer tout le contenu du répertoire
Comment tester les attributs ajoutés par add_request_method de pyramid
Comment utiliser le générateur
Comment se connecter automatiquement comme 1Password depuis CLI
(Note) Comment passer le chemin de votre propre module
Je souhaite calculer le temps d'arrêt autorisé à partir du taux de fonctionnement
Comment gratter le cours d'une action individuelle du site Web Nikkei Shimbun avec Python
Comment compter rapidement la fréquence d'apparition des caractères à partir d'une chaîne de caractères en Python?
Comment effectuer les réglages initiaux à partir de la création de projet Django
Comment résumer les résultats de FreeSurfer ~ aparc, aseg, wmparc ~
Comment exécuter automatiquement la fonction d'exportation de GCP Datastore
Comment calculer la somme ou la moyenne des données csv de séries chronologiques en un instant
Comment augmenter le nombre d'images de jeux de données d'apprentissage automatique
Comment connaître le nombre de GPU de python ~ Remarques sur l'utilisation du multitraitement avec pytorch ~
Comment accéder à NAPALM depuis le Web (solution réelle NetDevOpsSec)
Comment voir le contenu du fichier ipynb du notebook Jupyter
L'histoire de la copie de données de S3 vers TeamDrive de Google
Comment trouver le coefficient de mise à l'échelle d'une ondelette bipolaire
Calculez le nombre de changements
Après tout, l'histoire du retour de Linux à Windows
Comment représenter la distribution de la composition bactérienne à partir des données d'analyse Qiime2 dans un diagramme de moustaches
Comment utiliser le décorateur
Comment obtenir une liste de liens à partir d'une page de wikipedia
Comment augmenter l'axe
Comment démarrer la première projection