vijosP1447 开关灯泡

vijosP1447 开关灯泡

链接：https://vijos.org/p/1447

【思路】

数学+高精度。

分析题目：题中有言，i时刻将其所有倍数的灯熄灭，由此得知一个数有多少个倍数就会被操作多少次，因为初始全部熄灭，所以操作数为奇的灯最后会亮着，再进一步，只有序号为平方数的灯在最后会亮着。

由此题目转化为求n以内平方数的个数，个数为sqrt(n)个（别问我怎么知道的=_=）

数据范围要求我们用到高精。至此，题目就是对一个大数开方的问题，NOIP的初赛曾出现过这个程序。

【代码】

 #include<iostream>

 #include<cstring>

 #include<cmath>

 using namespace std;

 const int maxn = +;

 struct Bign{

     int len;

     int num[maxn];

     Bign() {  memset(num,,sizeof(num)); }

 };

 Bign goal;

 Bign times(Bign a,Bign b) {

     Bign c;

     c.len=a.len+b.len+;

     for(int i=;i<a.len;i++)

       for(int j=;j<b.len;j++)

         c.num[i+j] += a.num[i]*b.num[j];

     for(int i=;i<c.len-;i++) {

         c.num[i+] += c.num[i]/;

         c.num[i] %= ;

     }

     while(c.num[c.len-]==) c.len--;

     return c;

 }

 Bign average(Bign a,Bign b) {

     Bign c; c.len=max(a.len,b.len);

     for(int i=;i<c.len;i++) {

         c.num[i] += a.num[i]+b.num[i];

         c.num[i+] += c.num[i]/;

         c.num[i] %= ;

     }

     if(c.num[c.len]) c.len++;

     for(int i=c.len-;i;i--) {

         c.num[i-] += (c.num[i]%) *;

         c.num[i] /= ;

     }

     c.num[]/=;

     if(c.num[c.len-]==) c.len--;

     return c;

 }

 Bign plustwo(Bign a) {

     a.num[] += ;

     int i=;

     while(i<a.len && a.num[i]>=) {

         a.num[i+] += a.num[i]/;

         a.num[i] %= ;

         i++;

     }

     if(a.num[a.len]) a.len++;

     return a;

 }

 bool over(Bign a,Bign b) {

     if(a.len>b.len) return true;

     else if(a.len<b.len) return false;

     for(int i=a.len;i>=;i--) //倒序

       if(a.num[i]>b.num[i]) return true;

       else if(a.num[i]<b.num[i]) return false;

     return false;

 }

 int main() {

     ios::sync_with_stdio(false);

     string s;

     cin>>s;

     goal.len=s.size();

     for(int i=;i<goal.len;i++) goal.num[i]=s[goal.len--i]-'';

     Bign L , R=goal , M;

     L.len=; L.num[]=;

     do

      {

            M=average(L,R);

            if(over(times(M,M),goal)) R=M;

            else L=M;

     } while(! over(plustwo(L),R)) ;

     for(int i=L.len-;i>=;i--) cout<<L.num[i];

     return ;

 }