描述
一个房间里有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位的操作。这个过程需要用到大数乘法、减法、移位。
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;
}