Районная олимпиада 2019-2020 информатика
Задача D. Делители
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Вам дано целое число n. Найдите количество чисел от 1 до n, которые имеют четное количество делителей.
Формат входного файла
В первой строке одно целое число n (1<=n<=109).
Формат выходного файла
Выведите ответ.
Система оценки
Данная задача содержит 10 тестов. Каждый тест оценивается в 10 баллов:
- 1<=n<=1000. Тесты с номерами 1-6.
- 1<=n<=105. Тесты с номерами 7-8.
- 1<=n<=109. Тесты с номерами 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;
}
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.