下面是一位先贤评论的，太靠下了。我贴到上面来吧。
3144046cjc发表于2008-09-18 18:36
我来证明一下这个题目的结论.

假设我们已经求出(n-1)时的
答案为ans,这时添加第n盏灯,
显然不会影响原来(n-1)盏灯
里亮的数目,这样,如果n有奇
数个因子,则现在的答案为(ans+1),
否则现在的答案为ans.

什么样的数有奇数个因子呢?
答案是当且仅当n=x*x (x>=1).
证明
充分性:
将n写成如下形式:
n=q1^a1 * q2^a2 * q3^a3 **** qm^am
qi为质数,显然,所有的a 必然为偶数,否则n
不是平方数.
则n的因子个数c=(a1+1)*(a2+1)***(am+1) 为奇数,
证毕!
必要性:
如果n不是平方数,
那么 将n写成如下形式:
n=q1^a1 * q2^a2 * q3^a3 **** qm^am
a 不可能全部为偶数(如果都是偶数的话n就
明显是一个平方数了)
则n的因子个数c=(a1+1)*(a2+1)***(am+1) 必为偶数
证必!

即对于给定的输入n,
答案就是1..n中的平方数的个数.
很容易知道,答案为使下面不等关系成立的最小x:
(x+1)^2 >=n+1

描述
一个房间里有n盏灯泡，一开始都是熄着的，有1到n个时刻，每个时刻i，我们会将i的倍数的灯泡改变状态（即原本开着的现将它熄灭，原本熄灭的现将它点亮），问最后有多少盏灯泡是亮着的。
提示
范围：40%的数据保证，n<=maxlongint
100%的数据保证，n<=10^200
**********************************************************************
1.编个小程序，打表（1-30），可以看出规律 f(n)=sqrt(n)的下界。
2.思考如何求大整数的根号：两种思路：迭代法，例如二分法、牛顿迭代等；
打点法：精确计算，一步到位。笔算开平方法，我二姐教过我。真是太好了。
我只想简单说个大概：
i。从后往前，隔两位点一个小数点
ii。从前往后，试商，做差，落下来
3.打点法肯定速度非常快O(200*100)的复杂度：根最大是100位，每求一位最多200位的操作。这个过程需要用到大数乘法、减法、移位。----------15ms----------------
4.最后一点，在编大数运算时最好按照位数固定进行运算，这样虽然牺牲了一点效率，但可读性好、易于实现。
5.要背下来大数运算，不要只会抄scl，唯有如此，方能随用随写，剑心合一。
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
#define size 205
int n[205], ni;
int ans[205];
int now[205];
int two[205];
int mu[205];
void getTwo(){//two=(ans*2)<<1;
memset(two, 0, sizeof(two));
int i;
for (i = 0; i < size; i++){
two[i] += (ans[i] << 1);
two[i + 1] = two[i] / 10;
two[i] %= 10;
}
for (i = size - 2; i >= 0; i--)
two[i + 1] = two[i];
}
void getNow(){
int i;
for (i = size - 3; i >= 0; i--){
now[i + 2] = now[i];
}
now[1] = n[ni--];
now[0] = n[ni--];
}
void mul(int k){//mu=two_k*k
memset(mu, 0, sizeof(mu));
int i;
for (i = 0; i < size; i++){
mu[i] += two[i] * k;
mu[i + 1] = mu[i] / 10;
mu[i] %= 10;
}
}
int cmp(){//now-mu
int i;
for (i = size - 1; i >= 0; i--)
if (now[i] != mu[i])
return now[i] - mu[i];
return 0;
}
void sub(){//now-mu
int i;
for (i = 0; i < size - 1; i++){
now[i] -= mu[i];
if (now[i] < 0){
now[i + 1]--;
now[i] += 10;
}
}
}
void getAns(){
int i;
for (i = size - 2; i >= 0; i--){
ans[i + 1] = ans[i];
}
for (i = 9; i >= 0; i--){
two[0] = i;
mul(i);
if (cmp() >= 0){
ans[0] = i;
sub();
return;
}
}
}
void go(){
while (ni >= 0){
getTwo();
getNow();
getAns();
}
}
int main(){
freopen("in.txt", "r", stdin);
char a[205];
int i;
for (i = 0; a[i]; i++);
ni = i;
memset(n, 0, sizeof(n));
for (i = 0; i < ni; i++)
n[i] = a[ni - 1 - i] - '0';
if ((ni & 1) == 0)ni--;
memset(ans, 0, sizeof(ans));
memset(now, 0, sizeof(now));
go();
for (i = size - 1; ans[i] == 0; i--);
for (; i >= 0; i--)cout << ans[i];
return 0;
}

打表知答案为sqrt(n)下取整.
###Code
n=getint();
while(n--)
{
memset(a,0,sizeof(int)*n+4);

for(int i=1;i<=n;i++)
{

for(int j=i;j<=n;j+=i)
a[j]^=1;

//for(int i=1;i<=n;i++)
//cout<<a[i]; cout<<endl;
}

int cnt=0;
for(int i=1;i<=n;i++)
if(a[i]) cnt++;

cout<<n<<' '<<cnt<<endl;
}

然后上高精模板,牛顿迭代法做400次(模板写了除法为何不用2333)
###Code
for(int i=0;i<400;i++)
s=(s+(n/s))/2;

然后光荣地700msAC......

C++的大数模板要比java快很多啊……
```Java
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static int maxn = 1000 + 10;
public static void main(String[] args) {
Scanner Cin = new Scanner(System.in);
BigInteger two = BigInteger.valueOf(2);
BigInteger n = Cin.nextBigInteger();
BigInteger l = BigInteger.ONE;
BigInteger r = n;
BigInteger mid = l.add(r).divide(two);
while(l.compareTo(r) != 1) {
if(mid.multiply(mid).compareTo(n) == 1) {
r = mid.subtract(BigInteger.ONE);
mid = l.add(r).divide(two);
}else {
l = mid.add(BigInteger.ONE);
mid = l.add(r).divide(two);
}
// System.out.println(mid);
}
while(mid.multiply(mid).compareTo(n) != 1) {
mid = mid.add(BigInteger.ONE);
}
while(mid.multiply(mid).compareTo(n) == 1) {
mid = mid.subtract(BigInteger.ONE);
}
System.out.println(mid);
}
}
```

type tt=record
l:longint;
t:array [0..205] of longint;
end;
var
a,b,c,d,e:tt;
s:string;
l,i:longint;
function comp(a,b:tt):boolean;
var i:longint;
begin
if (a.l<b.l) then exit(true);
if (a.l>b.l) then exit(false);
for i:=a.l downto 1 do
begin
if (a.t[i]<b.t[i]) then exit(true);
if (a.t[i]>b.t[i]) then exit(false);
end;
exit(false);
end;
procedure mid;
var i,x,l:longint;
begin
fillchar(d,sizeof(d),0);
for i:=1 to c.l do d.t[i]:=b.t[i]+c.t[i];
for i:=1 to c.l do
begin
inc(d.t[i+1],d.t[i] div 10);
d.t[i]:=d.t[i] mod 10;
end;
if d.t[c.l+1]>0 then l:=c.l+1 else l:=c.l;
x:=0;
for i:=l downto 1 do
begin
x:=x*10+d.t[i];
d.t[i]:=x div 2;
x:=x mod 2;
end;
d.l:=l;
while (d.t[d.l]=0) and (d.l<>1) do dec(d.l);
end;
procedure square;
var i,j,x:longint;
begin
fillchar(e,sizeof(e),0);
for i:=1 to d.l do
begin
x:=0;
for j:=1 to d.l do
begin
x:=x+d.t[i]*d.t[j]+e.t[i+j-1];
e.t[i+j-1]:=x mod 10;
x:=x div 10;
end;
e.t[i+d.l]:=x;
end;
if (e.t[d.l*2]=0) then e.l:=d.l*2-1 else e.l:=d.l*2;
end;
procedure plus1;
var i:longint;
begin
b:=d; inc(b.t[1]);
for i:=1 to b.l do
begin
inc(b.t[i+1],b.t[i] div 10);
b.t[i]:=b.t[i] mod 10;
end;
if (b.t[b.l+1]<>0) then inc(b.l);
end;
procedure print(b:tt);
var i:longint;
begin
for i:=b.l downto 1 do write(b.t[i]);
writeln;
end;
procedure decc;
var i:longint;
begin
c:=b; dec(c.t[1]);
for i:=1 to c.l do
if (c.t[i]<0) then
begin
dec(c.t[i+1]);
c.t[i]:=c.t[i]+10;
end;
if (c.t[c.l+1]<>0) then dec(c.l);
end;
begin
readln(s); a.l:=length(s);
for i:=1 to a.l do a.t[i]:=ord(s[a.l-i+1])-48;
b.l:=1; b.t[b.l]:=1; c.l:=(a.l+3) div 2; c.t[c.l]:=1;
while comp(b,c) do
begin
mid; square;
if comp(e,a) then plus1 else c:=d;
end;
decc; print(c);
end.

我觉得模仿笔算开平方要简单一点。
200位的大数开平方，试商时试10次。复杂度为o（2000）
估计0ms的事。

高精度开根号
program p1447;
var a:array[0..400] of longint;
l,r,mid,mids:array[0..400] of longint;
s:string;
i,k:longint;
//
function mk:boolean;
var i:longint;
begin
if l[0]<>r[0] then exit(l[0]>r[0]);
i:=l[0];
while (l[i]=r[i]) and (i>=2) do dec(i);
exit(l[i]>r[i]);
end;
//
function km:boolean;
var i:longint;
begin
if mids[0]<>a[0] then exit(mids[0]<=a[0]);
i:=a[0];
while (mids[i]=a[i]) and (i>=2) do dec(i);
exit(mids[i]<=a[i]);
end;
//
function f1:longint;
var i:longint;
begin
l:=mid;inc(l[1]);
for i:=1 to l[0] do
begin
l[i+1]:=l[i+1]+(l[i] div 10);l[i]:=l[i] mod 10;
end;
if l[l[0]+1]>0 then inc(l[0]);
end;
//
function f2:longint;
var i:longint;
begin
r:=mid;dec(r[1]);
for i:=2 to r[0] do
if r[i-1]<0 then
begin
r[i-1]:=r[i-1]+10;dec(r[i]);
end else exit;
end;
//
procedure makemid;
var i,f:longint;
begin
fillchar(mid,sizeof(mid),0);
if l[0]>r[0] then f:=l[0] else f:=r[0];
for i:=1 to r[0] do mid[i]:=l[i]+r[i];
for i:=1 to r[0] do
begin
mid[i+1]:=mid[i+1]+(mid[i] div 10);mid[i]:=mid[i] mod 10;
end;
mid[0]:=f;
if mid[f+1]>0 then inc(mid[0]);
for i:=mid[0] downto 2 do
begin
mid[i-1]:=mid[i-1]+(mid[i] mod 2)*10;
mid[i]:=mid[i] div 2;
end;
mid[1]:=mid[1] div 2;
if mid[mid[0]]=0 then dec(mid[0]);
end;
//
procedure makemids;
var i,j:longint;
begin
fillchar(mids,sizeof(mids),0);
for i:=1 to mid[0] do
for j:=1 to mid[0] do mids[i+j-1]:=mids[i+j-1]+mid[i]*mid[j];
for i:=1 to mid[0]*2-1 do
begin
mids[i+1]:=mids[i+1]+(mids[i] div 10);mids[i]:=mids[i] mod 10;
end;
mids[0]:=mid[0]*2;while mids[mids[0]]=0 do dec(mids[0]);
end;
//
begin
read(s);
for i:=1 to length(s) do a[i]:=ord(s[i])-ord('0');a[0]:=length(s);
for i:=1 to a[0] div 2 do begin k:=a[i];a[i]:=a[a[0]-i+1];a[a[0]-i+1]:=k;end;
l[0]:=1;l[1]:=1;r:=a;
while not(mk) do
begin
makemid;
makemids;
if km then f1
else f2;
end;
for i:=r[0] downto 1 do write(r[i]);
end.

var
a:array[1..100000000] of longint;
i,j,n,m:longint;
begin
m:=0;
read(n);
for i:=1 to n do
a[i]:=-1;
for j:=1 to n do
for i:=1 to n do
begin
if i mod j= 0 then a[i]:=0-a[i];
end;
for i:=1 to n do
if a[i]=1 then m:=m+1;
write(m);
readln;
end.
为什么会超时

好像是在Zerojudge上看到过的Light,More Light

我的题解：

http://hi.baidu.com/%C4%BE%D7%D3%C8%D5%D4%C8/blog/item/ea841110d2ef3bcca7ef3f01.html

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

秒！

逐位枚举，68行

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

神牛的

代码

爽……

Orz 神牛

我抄……

高精开方才是王道！！！90行的程序，秒杀！！！

比我晚十分钟运行的都AC了，我的还在RUNNING！！！

为什么还在Running?

var

a:array[1..maxlongint]of boolean;

i,j,n,s:longint;

begin

readln(n);

for i:=1 to n do

for j:=1 to n div i do

a:=not(a);

for i:=1 to n do

if a[i]then s:=s+1;

writeln(s);

end.

能先数学算完全平方数，再在范围内输符合值哇？

130行的程序调试成功，成就感啊-_-!

谁让我是水鸟的。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：41ms

type

arr=array[0..401] of longint;

var

a,l,r:arr;

i,j,len:longint;

st:string;

function max(x,y:longint):longint;

begin

if x>y then exit(x)

else exit(y);

end;

function small(x,y:arr):boolean;

var

i:longint;

begin

if x[0]y[0] then exit(false);

for i:=x[0] downto 1 do

begin

if x[i]y[i] then exit(false);

end;

exit(false);

end;

function same(x,y:arr):boolean;

var

i:longint;

begin

if x[0]y[0] then exit(false);

for i:=x[0] downto 1 do

if x[i]y[i] then exit(false);

exit(true);

end;

function add(x,y:arr):arr;

var

i,le:longint;

begin

fillchar(add,sizeof(add),0);

le:=max(x[0],y[0]);

for i:=1 to le do

begin

inc(add[i],x[i]+y[i]);

inc(add,add[i] div 10);

add[i]:=add[i] mod 10;

end;

if add[le+1]>0 then inc(le);

add[0]:=le;

end;

function middle(x,y:arr):arr;

var

i,yu,t:longint;

begin

fillchar(middle,sizeof(middle),0);

middle:=add(x,y);

for i:=middle[0] downto 1 do

begin

yu:=yu*10;

t:=middle[i];

middle[i]:=(middle[i]+yu) div 2;

yu:=(t+yu) mod 2;

end;

if middle[middle[0]]=0 then dec(middle[0]);

end;

function plus(x,y:arr):arr;

var

i,j:longint;

begin

fillchar(plus,sizeof(plus),0);

for i:=1 to x[0] do

begin

for j:=1 to y[0] do

begin

inc(plus,x[i]*x[j]);

inc(plus,plus div 10);

plus:=plus mod 10;

end;

inc(plus,plus div 10);

plus:=plus mod 10;

end;

if plus[x[0]+y[0]]>0 then plus[0]:=x[0]+y[0]

else plus[0]:=x[0]+y[0]-1;

end;

procedure go;

var

mid,t:arr;

begin

fillchar(t,sizeof(t),0);

t[1]:=1;

t[0]:=1;

while not (same(r,l) or same(add(l,t),r)) do

begin

mid:=middle(l,r);

if small(plus(mid,mid),a) then

l:=mid

else r:=mid;

end;

end;

procedure print;

var

i:longint;

begin

if not same(plus(r,r),a) then

r:=l;

for i:=r[0] downto 2 do

write(r[i]);

writeln(r[1]);

end;

begin

readln(st);

len:=length(st);

for i:=1 to len do

a[len-i+1]:=ord(st[i])-48;

a[0]:=len;

l[0]:=1;

l[1]:=1;

r:=a;

go;

print;

end.

我是第300个AC这题的，~~~~~~~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

我是直接高精度开方的，

个人认为这样时间和编程复杂度都比二分低。