分析:使用的是构造新数字法进行不断构造,然后逼近每一位数字,然后使用c++徒手敲了240多行代码,竟然过了........................很有成就感。

代码如下:

===============================================================================================================================

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std; const int MAXN = ; struct BigNum
{///数值保存从0位开始
int Size;///数的位数
int num[MAXN];///数值,逆序保存 BigNum(){
Size=;
memset(num, false, sizeof(num));
}
void Cin()
{
char s[MAXN]; scanf("%s", s);
Size = strlen(s); for(int i=Size-; i>=; i--)
num[i] = s[Size-i-] - '';
}
bool operator <= (const BigNum &b)const
{
if(Size > b.Size)return false;
if(Size < b.Size)return true; for(int i=Size-; i>=; i--)
{
if(num[i] > b.num[i])return false;
if(num[i] < b.num[i])return true;
} return true;
}
void operator = (const BigNum &b)
{
Size = b.Size; for(int i=; i<b.Size; i++)
num[i] = b.num[i];
}
void operator = (const int &b)
{
int tem = b; if(b == )
Size = ;
else
Size = (int)(log10(tem)+0.00001)+; for(int i=; i<Size; i++)
{
num[i] = tem % ;
tem /= ;
}
}
BigNum operator <<(const int &k)const
{
BigNum tmp; for(int i=Size-; i>=; i--)
{
tmp.num[i+k] = num[i];
}
tmp.Size = Size + k; tmp.CarryBit(); return tmp;
}
BigNum operator * (const BigNum &b)const
{
BigNum res; res.Size = Size + b.Size - ; for(int i=; i<b.Size; i++)
for(int j=; j<Size; j++)
{
res.num[i+j] += num[j] * b.num[i];
} res.CarryBit(); return res;
}
BigNum operator * (const int &b)const
{
BigNum res; res.Size = Size; for(int i=; i<Size; i++)
{
res.num[i] = num[i] * b;
} res.CarryBit(); return res;
}
BigNum operator + (const BigNum &b)const
{
BigNum res;
res.Size = max(b.Size, Size); for(int i=; i<res.Size; i++)
res.num[i] = num[i] + b.num[i];
res.CarryBit(); return res;
}
BigNum operator + (const int &b)const
{
BigNum res;
res = b; res.Size = max(res.Size, Size); for(int i=; i<res.Size; i++)
res.num[i] += num[i];
res.CarryBit(); return res;
}
BigNum operator - (const BigNum &b)const
{///b值小,先比较在进行相减
BigNum res; res.Size = Size;
for(int i=; i<Size; i++)
{
if(i < b.Size)
res.num[i] = num[i] - b.num[i];
else
res.num[i] = num[i];
}
res.CarryBit(); return res;
}
void CarryBit()
{///进位,注意减法的时候进位结果需要是非负数
for(int i=; i<Size; i++)
{
if(num[i] >= )
{
if(i+==Size)
{
num[i+] = ;
Size += ;
} num[i+] += num[i]/;
num[i] %= ;
}
else if(num[i] < )
{
num[i+] -= ;
num[i] += ;
}
}
while(Size > && !num[Size-])
Size -= ;
}
void Out()
{
for(int i=Size-; i>=; i--)
printf("%d", num[i]);
printf("\n");
}
};
int Find(const BigNum &a, BigNum &Mod)
{
int i;
BigNum t; for(i=; i<=; i++)
{
t = (((a*)<<)+i) * i; if(t <= Mod)
continue;
break;
} i--;
t = (((a*)<<)+i) * i; Mod = Mod - t; return i;
}
BigNum Sqrt(const BigNum &a)
{
BigNum ans, Mod;
int len=a.Size-; if(a.Size % == )
{
Mod = Mod + (a.num[len]*+a.num[len-]);
len -= ;
}
else
{
Mod = Mod + a.num[len];
len -= ;
} ans = Find(ans, Mod); while(len > )
{
Mod = (Mod<<) + (a.num[len]*+a.num[len-]);
ans = (ans<<) + Find(ans, Mod); len -= ;
} return ans;
} int main()
{
BigNum a; a.Cin();
a = Sqrt(a); a.Out(); return ;
}

最新文章

  1. 打造android偷懒神器———ListView的万能适配器
  2. Z-STACK在CC2530上同时使用两个串口
  3. Linux学习笔记(2)-开机
  4. SpringMVC常用配置-Controller返回格式化数据如JSON、XML的配置方式和机制
  5. ICEM(1)—边界结构网格绘制
  6. iOS安全笔记
  7. [Unity] 常用技巧收集
  8. 关于List.ToArray()方法的效率测试
  9. 文本读写vs二进制读写
  10. jsp空页面导致的jvm heap溢出
  11. References &amp; the Copy-Constructor
  12. codevs 1153 道路游戏
  13. .NET程序集签名
  14. Ajax 学习笔记
  15. mysql数据库-注释相关介绍
  16. Nginx原理和配置总结
  17. obj-c编程17:键值观察(KVO)
  18. python 去除html 超链接href 如何实现?
  19. linux定时清理日志
  20. servlet保存会话数据---利用隐藏域

热门文章

  1. tomcat环境变量配置
  2. 系统设计 - IOS 程序插件及功能动态更新思路
  3. php session 自定义的设置测试
  4. 1.document.write(&quot;&quot;); 输出语句
  5. JavaScript OOP 创建对象的7种方式
  6. CocoaPods ADD private Spec Repo
  7. WebApi学习总结系列第五篇(消息处理管道)
  8. QueryRunner的使用
  9. &quot;Invalid bound statement (not found): com.sitech.admin.dao.TbOpenAbilityInfoDao.findAbilityReadyUp&quot;mybatis配置文件bug
  10. Hive的Metastore contains multiple versions