背景 Background
清北学堂杯Tyvj2周年邀请赛 第三道描述 Description
VNB从小立志当一名杰出的数学家。有一天，admin给了VNB一个任务：求int(√1)+int(√2)+……+int(√n)的值是多少。VNB 以为很简单，就接下了这个任务，但是当他看到n的范围大小就傻眼了。所以，他打着“节约计算用纸以保护地球”的口号向你发出了求救。注： int(x)表示实数x的整数部分。
再注：VNB怕你算太长时间，就先帮你算出了int(√n)的大小，来帮助你更好的完成此题。
输入格式 InputFormat
共两行每行一个正整数分别为N和 K，K表示int(√n)
输出格式 OutputFormat
仅一行一个正整数，为int(√1)+int(√2)+……+int(√n)的值。样例输入 SampleInput [复制数据]
10
3
样例输出 SampleOutput [复制数据]
19
数据范围和注释 Hint
30%的数据k<=2*10^6(保证结果在int64 or comp以内)
90%的数据k<=10^100
所有的数据保证k<=10^10000 k^2<=n<(k+1)^2
思路：这道题是我两年前用pascal写过的最长的一道题了，，但是当时还不会压位，最后一个点还T了，现在好多了，通项公式：ans=(6*k*n-2*k*k*k-3*k*k+5k)/6;
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int maxn=4020,maxl=4000,ml=4010;
const ll mod=100000000;
ll a[ml],b[ml],c[ml],kn6[ml],six[ml],k[ml],n[ml],k2[ml];
ll ans[ml],kkk2[ml],kk3[ml],k5[ml],five[ml];
ll two[ml],three[ml];
ll t,add;
int h;
char kk[maxn*10],nn[maxn*10];
void close()
{
exit(0);
}
void mul(ll *a,ll *b,ll *c)
{
int reach;
for (reach=0;a[reach]==0 && reach<=maxl;reach++);
for (int i=maxl;i>=reach;i--)
{
h=i;
for (int j=maxl;j>=1;j--)
{
if (h==1) break;
t=a[i]*b[j];
c[h]+=t;
c[h-1]+=c[h] / mod;
c[h] %= mod;
h--;
}
}
}
void muls(ll *a,int v)
{
add=0;
for (int i=maxl;i>=1;i--)
{
t=add+a[i]*v;
a[i]=t % mod;
add=t / mod;
}
}
void plus(ll *a,ll *b,ll *c)
{
add=0;
for (int i=maxl;i>=1;i--)
{
t=a[i]+b[i]+add;
c[i]=t % mod;
add=t / mod;
}
}
void sub(ll *a,ll *b,ll *c)
{
add=0;
for (int i=maxl;i>=1;i--)
{
t=a[i]-b[i];
if (t<0)
{
a[i-1]--;
t+=mod;
}
c[i]=t;
}
}
void divide(int div,ll *a,ll *b)
{
t=0;add=0;
for (int i=1;i<=maxl;i++)
{
t=add * mod+a[i];
b[i]=t / div;
add=t % div;
}
}
void print(ll *a)
{
int i;
for (i=0;i<maxl && a[i]==0;i++);
printf("%lld",a[i]);
if (i==maxl) printf("
");
for (int j=i+1;j<=maxl;j++)
{
printf("%08lld",a[j]);
if (j==maxl)
printf("
");
}
}
void work()
{
mul(k,n,kn6);
muls(kn6,6);
/////////////////////
mul(k,k,kk3);
mul(kk3,k,kkk2);
muls(kkk2,2);
////////////////////
memset(a,0,sizeof(a));
muls(kk3,3);
////////////////////////
memcpy(k5,k,sizeof(k));
muls(k5,5);
/////////////////////
plus(kn6,k5,ans);
sub(ans,kkk2,ans);
sub(ans,kk3,ans);
divide(6,ans,ans);
print(ans);
/*
mul(k,n,kn6);
memset(six,0,sizeof(six));
six[maxl]=6;
mul(kn6,six,kn6);
print(kn6);
close();
//--------------------------
mul(k,k,kkk2);//k*k->kkk
mul(kkk2,k,kkk2);//k*k*k->kkk
two[maxl]=2;
mul(kkk2,two,kkk2);//2*k*k*k->kkk
//--------------------------
mul(k,k,kk3);//k*k->kk3
three[maxl]=3;
mul(kk3,three,kk3);//k*k*3->kk3
//-------------------------------
memset(five,0,sizeof(five));
five[maxl]=5;
mul(k,five,k5);//k*5->k5
//-------------------------------
plus(kn6,k5,ans);
sub(ans,kkk2,ans);
sub(ans,kk3,ans);
divide(6,ans,ans);
print(ans);
printf("Real Answer:%d
",(6*kk*nn-kk*kk*kk*2-kk*kk*3+5*kk)/6);
printf("kn6:%d
",6*kk*nn);
printf("kkk2:%d
",kk*kk*kk*2);
printf("kk3:%d
",kk*kk*3);
printf("k5:%d
",kk*5);
printf("1 step:%d
",6*kk*nn+kk*5);
printf("%d
",6*kk*nn+kk*5-kk*kk*kk*2);
printf("%d
",6*kk*nn+kk*5-kk*kk*kk*2-kk*kk*3);
*/
}
void convert(char *s,ll *b)
{
int l=strlen(s),rec=0;
h=maxl;
t=1;add=0;
for (int i=l-1;i>=0;i--)
{
rec++;
add+=t*(s[i]-'0');
t*=10;
if (rec==8)
{
rec=0;
b[h]=add;
add=0;
t=1;
h--;
}
}
if (add!=0) b[h]=add;
}
void init()
{
scanf("%s %s",nn,kk);
convert(nn,n);
convert(kk,k);
work();
}
int main ()
{
init();
close();
return 0;
}