How to calculate the amount of calculation learned from ABC134-D

problem

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

was difficult. Or rather, it was difficult to read the problem statement.

This lesson

  1. Arbitrary integer = nuance like all integers
  2. Uniquely confirmed by solving in order from the back
  3. O(\sum(N/i)) = O(NlogN)

How to calculate the amount of calculation

Question raised: Is $ O (\ sum (N / i)) $ in time?

In this problem, it is necessary to find $ N / i $ at any i. When considering this, it is good to perform integration. Since $ \ int (1 / N) = logN $, it can be suppressed by logN at worst.

Summary

  1. Become a mathematical sentence
  2. It is common to judge an array from the front or the back, and you have to be aware of it.
  3. ** Considering the integral, the calculation time can be obtained from the area. ** **

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

How to calculate the amount of calculation learned from ABC134-D
How to calculate the autocorrelation coefficient
How to find the average amount of information (entropy) of the original probability distribution from a sample
How to check the version of Django
How to calculate Use% of df command
How to operate Linux from the console
How to access the Datastore from the outside
From the introduction of GoogleCloudPlatform Natural Language API to how to use it
How to find the area of the Voronoi diagram
Change the decimal point of logging from, to.
How to operate Linux from the outside Procedure
How to measure line speed from the terminal
From the introduction of pyethapp to the execution of contract
The story of moving from Pipenv to Poetry
[Numpy, scipy] How to calculate the square root of a semi-fixed definite matrix
[Python] How to remove duplicate values from the list
How to know the port number of the xinetd service
The wall of changing the Django service from Python 2.7 to Python 3
Calculate volume from the two-dimensional structure of a compound
How to get the number of digits in Python
Calculation of the minimum required number of votes from turnout
How to solve the recursive function that solved abc115-D
The idea of Tensorflow learned from potato chip manufacturing
How to instantly launch Jupyter Notebook from the terminal
Steps to calculate the likelihood of a normal distribution
[Blender] How to dynamically set the selection of EnumProperty
[Python] Summary of how to specify the color of the figure
How to use the model learned in Lobe in Python
How to hit the document of Magic Function (Line Magic)
How to access the global variable of the imported module
How to post a ticket from the Shogun API
[Selenium] How to specify the relative path of chromedriver?
[Python] How to calculate the approximation formula of the same intercept 0 as Excel [scikit-learn] Memo
Summary from the beginning to Chapter 1 of the introduction to design patterns learned in the Java language
How to increase the processing speed of vertex position acquisition
[Ubuntu] How to delete the entire contents of a directory
How to test the attributes added by add_request_method of pyramid
How to use the generator
How to log in automatically like 1Password from the CLI
(Note) How to pass the path of your own module
I want to calculate the allowable downtime from the operating rate
How to scrape stock prices of individual stocks from the Nikkei newspaper website with Python
How to quickly count the frequency of appearance of characters from a character string in Python?
How to do the initial setup from Django project creation
How to summarize the results of FreeSurfer ~ aparc, aseg, wmparc ~
How to run the Export function of GCP Datastore automatically
How to calculate the sum or average of time series csv data in an instant
How to increase the number of machine learning dataset images
How to know the number of GPUs from python ~ Notes on using multiprocessing with pytorch ~
How to hit NAPALM from the Web (NetDevOpsSec reality solution)
How to see the contents of the Jupyter notebook ipynb file
The story of copying data from S3 to Google's TeamDrive
How to find the scaling factor of a biorthogonal wavelet
Calculate the number of changes
After all, the story of returning from Linux to Windows
What beginners learned from the basics of variables in python
How to plot the distribution of bacterial composition from Qiime2 analysis data in a box plot
How to use the decorator
How to get a list of links from a page from wikipedia
How to increase the axis
How to start the program