Районная олимпиада 2019-2020 информатика

Задача D. Делители

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Вам дано целое число $n$. Найдите количество чисел от $1$ до $n$, которые имеют четное количество делителей.

Формат входного файла

В первой строке одно целое число $n$ $(1 <= n <= 10^9)$.

Формат выходного файла

Выведите ответ.

Система оценки

Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:

1. $1 <= n <= 1000$. Тесты с номерами 1-6.
2. $1 <= n <= 10^5$. Тесты с номерами 7-8.
3. $1 <= n <= 10^9$. Тесты с номерами 9-10.

Пример:

Вход

10

Ответ

7

Замечание

В примере:

1. У числа $1$ делители: $1$. Количество $1$ - нечетно.
2. У числа $2$ делители: $1, 2$. Количество $2$ - четно.
3. У числа $3$ делители: $1, 3$. Количество $2$ - четно.
4. У числа $4$ делители: $1, 2, 4$. Количество $3$ - нечетно.
5. У числа $5$ делители: $1, 5$. Количество $2$ - четно.
6. У числа $6$ делители: $1, 2, 3, 6$. Количество $4$ - четно.
7. У числа $7$ делители: $1, 7$. Количество $2$ - четно.
8. У числа $8$ делители: $1, 2, 4, 8$. Количество $4$ - четно.
9. У числа $9$ делители: $1, 3, 9$. Количество $3$ - нечетно.
10. У числа $10$ делители: $1, 2, 5, 10$. Количество $4$ - четно.

( Aibar Kuanyshbay )

Комментарий/решение

показать/скрыть код

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n , ans = 0;
    cin >> n;
    ans = n;
    for (int i=1; i*i<=n; i++) ans--;
    cout <<ans;
}

C++

Copy

показать/скрыть код

#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define fi first
#define se second
using namespace std;
ll cal;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll n; cin>>n;
	ll cal = n;
    for(int i=1;i<=sqrt(n);i++)--cal;
    cout<<cal;
	return 0;}

C++

Copy

#include<iostream>

#include<cmath>

using namespace std;

int main(){

long long int a,b;

cin>>a;

b=sqrt(a);

cout<<a-b;

}

DELETED

показать/скрыть код

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define y1 asdasd

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector < int > vi;
typedef vector < ll > vll;
typedef set < int > si;
const int N = 2e5 + 123;
const int N2 = 1e6 + 123;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll VERYINF = 1e18 + 5;
const double pi = 3.141592653589;

int n;

int main () {
    start
    cin >> n;
    cout << n - (int)sqrt(n);
    return 0;
}
/*

*/

C++

Copy

показать/скрыть код

code
N = int(input())
Sum = 0
for i in range(1,N+1):
    SumI = 0
    for j in range(1, i+1):
        if i % j == 0:
            SumI += 1
    if SumI % 2 == 0:
       Sum += 1
print(Sum)
code

C++

Copy

показать/скрыть код

code
N = int(input())
Sum = 0

for i in range(1,N+1):

SumI = 0

for j in range(1, i+1):

if i % j == 0:

SumI += 1

if SumI % 2 == 0:

Sum += 1

print(Sum)
code

C++

Copy

#pragma GCC optimize("03")

#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define ll long long

#define pb push_back

#define mp make_pair

#define endl "\n"

#define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define rt return

#define sp " "

#define S second

#define F first

#define gcd(a, b) __gcd((a),(b))

#define lcm(a, b) ((a)*(b))/__gcd((a),(b))

const int inf = 1e5;

const int mod = 1000000007;

using namespace std;

int main()

{

int n;

cin>>n;

int nn = sqrt (n);

cout<<n-nn;

}

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n;

cin>>n;

//int x;

int x=sqrt(n);

cout<<n-x;

}

показать/скрыть код

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define russian setlocale(LC_ALL, "Russian_Russia.20866");
#define file freopen("bridges.in", "r", stdin), freopen("bridges.out", "w", stdout);
#define ll long long
#define dl double long
#define all(s) s.begin(), s.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
using namespace std;
const ll N = 200010;
ll ans;
int main() {
    speed;
    russian;
    //file;
    ll n;
    cin >> n;
    cout << n - (int)sqrt(n) << '\n';
}

C++

Copy