中南林业科技大学第十一届程序设计大赛 有趣的数字 牛客网
链接：https://www.nowcoder.com/acm/contest/124/D
来源：牛客网
题目描述
最近TreeDream沉迷于数字游戏中，发现了一种有趣的数字，有趣的数字定义如下：
给定一组n个数，a[1],a[2],a[3],...,a[n], 初始全为0，现在，在这组数上进行x操作；
x 操作定义如下：
x从1~n依次增加，每次把x的下标的倍数的数进行反转，0变成1,1变成0，操作完后，如果a[i]为0，那么i则是有趣的数。
现在对于给定的n（n<=1e15），求这时候有趣的数的个数。
例如：
n = 3
x = 1 时 ：a[1] = 1, a[2] = 1, a[3] = 1;
x = 2 时 ：a[1] = 1, a[2] = 0, a[3] = 1;
x = 3 时 ：a[1] = 1, a[2] = 0, a[3] = 0;此时，3个数中，有两个数为0，故有趣的数的个数为2；
输入描述:
多组样例，每个样例占一行，每一行输入一个数n，表示有n个数。（n<=1e15）
输出描述:
每个样例输出一行，一行输出一个数，表示有趣的数的个数。
示例1
1、sql 四舍五入保留两位小数
2、《Linux内核设计与实现》读书笔记(11)--- 内存管理(1)
3、前端工程师所具备的技能以及顺序
4、Oracle知识图
5、基于 django 自带的用户认证进行用户认证
输入
复制3
输出
复制2
emmmmm，这题暴力做不了，开始写的时候想了很久方法都写不出。最后看别人的博客打表找的规律。
规律是 n的时候结果是 n - (long long)sqrt(n)
#include<map> #include<queue> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define debug(a) cout << #a << ": " << a << endl; using namespace std ; const int maxn = 1e4 + 20 ; typedef unsigned long long ll; int main() { ios::sync_with_stdio(false); ll n; while( cin >> n ) { cout << n - ( ll )sqrt(n) << endl; } return 0 ; }优质内容筛选与推荐>>
1、sql 四舍五入保留两位小数
2、《Linux内核设计与实现》读书笔记(11)--- 内存管理(1)
3、前端工程师所具备的技能以及顺序
4、Oracle知识图
5、基于 django 自带的用户认证进行用户认证