Районная олимпиада 2019-2020 информатика
Задача D. Делители
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Вам дано целое число $n$. Найдите количество чисел от $1$ до $n$, которые имеют четное количество делителей.
Формат входного файла
В первой строке одно целое число $n$ $(1 <= n <= 10^9)$.
Формат выходного файла
Выведите ответ.
Система оценки
Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:
- $1 <= n <= 1000$. Тесты с номерами 1-6.
- $1 <= n <= 10^5$. Тесты с номерами 7-8.
- $1 <= n <= 10^9$. Тесты с номерами 9-10.
Пример:
Вход 10Ответ
7
Замечание
В примере:
- У числа $1$ делители: $1$. Количество $1$ - нечетно.
- У числа $2$ делители: $1, 2$. Количество $2$ - четно.
- У числа $3$ делители: $1, 3$. Количество $2$ - четно.
- У числа $4$ делители: $1, 2, 4$. Количество $3$ - нечетно.
- У числа $5$ делители: $1, 5$. Количество $2$ - четно.
- У числа $6$ делители: $1, 2, 3, 6$. Количество $4$ - четно.
- У числа $7$ делители: $1, 7$. Количество $2$ - четно.
- У числа $8$ делители: $1, 2, 4, 8$. Количество $4$ - четно.
- У числа $9$ делители: $1, 3, 9$. Количество $3$ - нечетно.
- У числа $10$ делители: $1, 2, 5, 10$. Количество $4$ - четно.
Комментарий/решение:
#include<iostream>
#include<cmath>
using namespace std;
int main(){
long long int a,b;
cin>>a;
b=sqrt(a);
cout<<a-b;
}
#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;
}
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.