[POI 22 Stage 1] Kwadraty

題目大意：

對於一個正整數 n ，有一些方法可以把他拆成相異正整數的平方和（也有可能沒辦法拆），考慮所有的拆法，令 k( n ) 代表最小的值，使得存在一種把 n 拆成相異正整數平方和的拆法，拆出來的每個數都<=k( n ) 。也就是「所有拆法中的最大值的最小值」（若 n 沒有任何拆法，則 k( n ) = 無限大）。我們稱一個數 x 是好的，若且唯若存在一個數 y > x 使得 k( y ) < k( x ) 。輸入一個 n ，輸出兩個數字，第一個數字代表 k( n ) ，第二個數字代表 1 ~ n 之中有幾個數是好的。若 k( n ) 為無限大則輸出一個 - 號。

作法：

這題應該算是找規律題。一開始可以先測試一下，會發現 1^2 , 2^2 , ... , 1000^2 可以湊出 10^6 以內的大部分的數，除了以下幾個數例外：2 , 3 , 6 , 7 , 8 , 11 , 12 , 15 , 18 , 19 , 22 , 23 , 24 , 27 , 28 , 31 , 32 , 33 , 43 , 44 , 47 , 48 , 60 , 67 , 72 , 76 , 92 , 96 , 108 , 112 , 128 ，之後把這些數形成的集合叫作 A 。所以可以猜說所有正整數裡面沒有辦法被拆成數個相異正整數平方和的數就只有這幾個。再來測試 1^2 , ... , n^2 可以湊出哪些數字，以下記 f( n ) = 1^2 + 2^2 + ... + n^2 = n * (n + 1 ) * (2 * n + 1) / 6 ，那麼會發現當 n 夠大的時候（大概20就可以了），這些數沒辦法湊出來的數只有 A 裡的數，還有 f( n ) 扣掉 A 裡的數，所以就可以推到這些數的 k 值會 >= n + 1 ，而可以被湊出來的數們的 k 值就會 <= n 。由這件事就可以得到只要一個數形如 f( n ) - a ，其中 a ∈ A ，那麼他就會是好的（因為 k( f( n ) ) = n）。並且會發現在 f( n - 1 ) + 1 到 f( n ) 之間只有這些數的 k 值是 n + 1 ，其他數的 k 值都是 n ，所以就可以利用這個規律得到解了。但要注意到的是前面講的那些規律都是在 n 不會太小的時候才會成立的（可以想到大概是因為 A 裡面有一個 128），所以在判斷比較小的數字是否是好的就只要直接算出他們的 k 值就可以了。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=10000+10 ;
int num[40]={2,3,6,7,8,11,12,15,18,19,22,23,24,27,28,31,
32,33,43,44,47,48,60,67,72,76,92,96,108,112,128} ;
bool d[maxn] ;
int k[maxn],ans[maxn] ;
 
main()
{
    fill(k,k+maxn,maxn) ;
    d[0]=1 ;
    for(int i=1;i<=100;i++) for(int j=maxn-1;j>=i*i;j--)
        if(!d[j] && d[j-i*i]) d[j]=1 , k[j]=i ;
    for(int i=1;i<=1000;i++) for(int j=i+1;j<maxn;j++)
        if(k[j]<k[i]) { ans[i]=1 ; break ; }
    for(int i=1;i<=1000;i++) ans[i]+=ans[i-1] ;
 
    LL n ; scanf("%lld",&n) ;
    if(n<=600)
    {
        if(k[n]==maxn) printf("- ") ;
        else printf("%d ",k[n]) ;
        printf("%d\n",ans[n]) ;
        return 0 ;
    }
 
    LL now=0 , x=0 ;
    for(;now<n;x++,now+=x*x) ; x-- ;
    LL ans1=x+1 ;
    for(int i=0;i<31;i++) if(now-num[i]==n) ans1=x+2 ;
    LL ans2=ans[506]+(x-10)*31 ;
    for(int i=0;i<31;i++) if(now-num[i]>n) ans2-- ;
    printf("%lld %lld\n",ans1,ans2) ;
}