题目描述

考虑将正整数n拆分成几个不同的平方数之和，比如30=1^2 + 2^2 + 5^2=1^2 + 2^2 + 3^2 + 4^2，而8不存在这样的拆分。 用k(n)表示n的拆分中，最大的底数最小可能是多少。如果n不存在这样的拆分，> 则令k(n)=∞。例如，k(1)=1,k(8)=∞,k(378)=12,k(380)=10。 定义一个数x被称为“超重”的，当且仅当存在y>x，使得k(y)<k(x)。从上面的例子可知，378是一个“超重”的数。 给定n，你需要：(1)求出k(n)(2)求出1~n中有几个“超重”的数。

输入输出格式

输入格式：

输入仅一行，包含一个正整数n(1<=n<=10^18)。

输出格式：

输出一行包含两个整数，分别为对上述两个问题的答案。如果k(n)=∞，则输出一个减号’-‘代替。

输入输出样例

输入样例#1：

30

输出样例#1：

4 15

说明

Orz，Claris的题解！

应该很容易理解。。。

#include<cstdio> #define N 507 typedef long long ll; ll n,l=12,r=1442250,mid,t,ans; int i,j,v[N],sum[N],f[N]={0,1,0,0,2,2,0,0,0,3,3,0,0,3,3,0,4,4,0,0,4,4,0,0,0,4,4,0,0,4,4,0,0,0,5,5,6,6,5,5,6,5,5,0,0,5,5,0,0,6,5,5,6,6,5,5,6,6,7,7,0,6,6,7,8,6,6,0,8,7,6,6,0,8,6,6,0,6,6,7,8,6,6,7,7,7,6,6,7,7,6,6,0,8,7,7,0,9,7,7,7,7,7,7,7,7,7,9,0,8,7,7,0,8,7,7,8,8,8,7,7,8,8,7,7,8,7,7,0,8,7,7,9,8,8,7,7,9,8,7,7,8,8,8,9,8,8,8,8,8,8,8,8,8,8,8,9,10,8,8,9,9,8,8,8,8,8,8,8,8,8,9,9,10,8,8,9,10,8,8,9,9,9,8,8,9,9,8,8,10,8,8,9,10,8,8,9,9,9,8,8,9,9,8,8,9,9,9,9,10,9,9,9,10,9,9,9,9,10,9,9,9,9,9,9,10,9,9,9,9,9,9,9,9,9,9,9,10,10,9,9,10,10,9,9,9,9,9,9,9,9,9,10,10,10,9,9,11,10,9,9,10,10,10,9,9,10,10,9,9,10,9,9,11,10,9,9,11,10,10,9,9,10,10,9,9,10,10,10,11,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,10,10,10,11,10,10,10,10,11,10,10,10,10,10,10,11,10,10,10,10,10,10,10,10,10,10,10,11,11,10,10,11,11,10,10,10,10,10,10,10,10,10,11,11,11,10,10,11,11,10,10,11,11,11,10,10,11,11,10,10,11,10,10,11,11,10,10,11,12,11,10,10,11,11,10,10,11,11,11,11,11,11,11,11,12,11,11,11,12,11,11,11,11,11,11,11,11,11,11,11,12,11,11,11,12,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,11,11,11,12,11,11,11,11,12,11,11,11,11,11,11,12,11,11,11,11,11,11,11,11,11,11,11,12,12,11,11,12,12,11,11,11,11,11,11,11,11,11,12,12,12,11,11,12,12,11,11,12,12,12,11,11,12,12,11,11,12,11,11,12,12,11,11,12,12,12,11,11,12,12,11,11}; ll F(ll x){return x*(x+1)*(x*2+1)/6;} int main(){ scanf("%lld",&n); for(i=2;i<N;i++)if(f[i])for(j=1;j<i;j++)if(!f[j]||f[j]>f[i])v[j]=1; for(i=2;i<N;i++)sum[i]=sum[i-1]+v[i]; if(n<N){ if(f[n])printf("%d",f[n]);else putchar('-'); return printf(" %d",sum[n]),0; } while(l<=r)if(F(mid=(l+r)>>1)>=n)r=(t=mid)-1;else l=mid+1; printf("%lld ",t+(F(t)>n&&F(t)-n<=128&&!f[F(t)-n])); for(ans=(t-12)*31+sum[N-1],i=1;i<=128;i++)if(!f[i]&&F(t)-i<=n)ans++; return printf("%lld",ans),0; } border="0" width="330" height="86" src="//music.163.com/outchain/player?type=2&id=41416774&auto=1&height=66">