51nod 1717 好数

1717 好数 基准时间限制：1 秒 空间限制：131072 KB 分值: 40  难度：4级算法题 有n个数  a[1],a[2],...,a[n]开始都是0 现在进行操作 t从1~n依次增加 每次把下标时t的倍数的数都反转（0变成1,1变成0）  如果最后a[i]为0，那么称此时的i为好数。 现在对于给定的n，求这时候的好数个数。 n<=1e15 Input 一个数n，表示有n个数。（n<=1e15） Output 一个数，表示好数的个数。 Input示例 2 Output示例 1

解题思路：枚举一部分数据，然后找规律，发现只有当i是完全平方数的时候最后才会变成1的，剩下的全部是0，则最后好数的个数就是n-sqrt(n)。。。注意输入输出都用long long

代码如下：

打表函数：

// for(int i=1;i<=30;i++) // printf("%d ",i); // printf("\n"); // for(int i=1;i<=30;i++) // { // for(int j=i;j<=30;j++) // if(j%i==0) a[j]= !a[j] ? 1 : 0; // for(int i=1;i<=30;i++) // printf("%d ",a[i]); // printf("\n"); // // } AC代码：

#include <stdio.h> #include <math.h> int main() { long long n; scanf("%lld",&n); printf("%lld\n",n-(long long)sqrt(n)); return 0; }