题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1337 杭电
http://poj.org/problem?id=1218清华
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1350浙江
原本以为小小的一道水题不值得去总结，但是发现却有好多方法，好神奇啊
方法一：数据挺小的模拟就好
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std; int a[110];
int main()
{
int t, n;
scanf("%d", &t);
while(t--)
{
memset(a, 0, sizeof(a));
scanf("%d", &n);
for(int i=1; i<=n; i++)
{
for(int j=i; j<=n; j+=i)
{
a[j]=a[j]^1;
}
}
int ans=0;
for(int i=1; i<=n; i++)
{
if(a[i]==1)
ans++;
} printf("%d\n", ans);
}
return 0;
}
方法二：其实犯人是否能够逃跑是有规律可循的，门有开/关两种形式，只要犯人最终开和关的总次数是奇数就好；例如3 1开3关 ，开关总和为偶数； 例如4 1开2关4开，开关总和为奇数 其实就是看一个数是否有奇数个因子；
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std; int solve(int x)
{
int cnt=;
for(int i=; i<=x; i++)
{
if(x%i==)
cnt++;
}
if(cnt%==)
return ;
else
return ;
}
int main()
{
int t, n;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
int ans=;
for(int i=; i<=n; i++)
{
if(solve(i))
ans++;
}
printf("%d\n", ans);
}
return ;
}
第三种：是看别人才知道的，真的是世界之大无奇不有；
原理是：只有完全平方数才有奇数个因子，例如3， 9，所以只需要求出n以内的完全平方数的个数即可；
n以内的 完全平方数的个数=sqrt(n);
#include<cstdio>
#include<cmath>
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",(int)sqrt(n));
}
return 0;
}