思路：先枚举 a*bas +b = n 求出 bas 在sqrt（n）到n的 （bas>a&&bas>b）
再枚举 a*bas*bas+b*bas+c =n 求出bas 在 n^(1/3) 到sqrt（n）的 （bas >a&&bas>b&&bas>c）
上面 a b c 均只有 3 4 5 6 四种取值。
剩下的 直接 n^(1/3) 枚举 效率为 n的三分之一 次方。
//============================================================================ // Name : 1003.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<cstdio> #define LL long long #define MAXN 1000050 using namespace std; LL ans[MAXN]; int f[]={3,4,5,6}; int main() { int tt,ri=0; LL n; scanf("%d",&tt); while(tt--) { int tail=0; scanf("%I64d",&n); if(n>=3&&n<=6) { printf("Case #%d: -1 ",++ri); continue; } if(n<3) { printf("Case #%d: %d ",++ri,tail); continue; } for(LL i=0;i<4;++i) { for(LL j=0;j<4;++j) { if((n-f[j])%f[i]==0&&(n-f[j])/f[i]>f[i]&&(n-f[j])/f[i]>f[j]) ans[tail++]=(n-f[j])/f[i]; } } for(LL i=0;i<4;++i) { for(LL j=0;j<4;++j) { for(LL k=0;k<4;++k) { LL l,r; l=4,r=2000100; LL ii=f[i]; LL jj=f[j]; LL kk=f[k]; while(r-l>1) { LL x=(l+r)>>1; LL cal=ii*x*x+jj*x+kk; if(cal>=n)r=x; else l=x; } if(ii*l*l+jj*l+kk==n&&l>f[i]&&l>f[j]&&l>f[k]) ans[tail++]=l; if(ii*r*r+jj*r+kk==n&&r>f[i]&&r>f[j]&&r>f[k]) ans[tail++]=r; } } } for(LL i=4;i*i*i<=n;++i) { LL x=n; int flag=1; while(x) { LL tmp=x%i; if(tmp<3||tmp>6) flag=0; x/=i; } if(flag) ans[tail++]=i; } sort(ans,ans+tail); tail=unique(ans,ans+tail)-ans; printf("Case #%d: %d ",++ri,tail); } return 0; }