[TIOJ][數論] 1349 - [特別加考題] 平方國的平方幣

[特別加考題] 平方國的平方幣

Time Limit:5000MS  Memory Limit:65536K
Total Submit:295 Accepted:64
Case Time Limit:3000MS

Description

平方國的人民對於完全平方數總是情有獨鍾。

就拿他們的貨幣來說吧，平方幣的幣值永遠是完全平方數，而且你所想像的任何完全平方幣值都有。

不過當外地旅客到平方國旅遊的時候，付錢卻成了令人頭痛的問題，當地人稱呼這種現象叫做「平幣效應」。

是的，你必須打破這種效應，於是你決定了，不管是任何金額，你總是可以支付最少張數的錢幣。

寫個程式吧，算起來比較快！ 

Input

輸入可能包含多筆測試資料，每一筆測試資料佔一列，僅包含一個正整數 N (1<=N<=10,000,000)。
當N=0時代表輸入結束。

Output

請輸出用最少幾張平方幣可以湊出該輸入金額。

Sample Input

1
2
3
4
5
6
7
0

Sample Output

1
2
3
1
2
3
4

Source

Problem Setter: Tmt
EXTREME version of Ural 1073
------------------------------------------------------------------------------------------------------------
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
int s[10000005]={0};
int main(){
    int n,i,j,add,check;
    for(i=1;i<=3162;i++){
        s[i*i]=1;
    }
    for(i=1;i<=3162;i++){
        for(j=i;j<=3162;j++){
            if(i*i+j*j>10000000) break;
            if(s[i*i+j*j]==0) s[i*i+j*j]=2;
        }
    }
    for(i=1;i<=10000000;i*=4){
        for(j=0;i*8*j+i*7<=10000000;j++)
            if(s[i*8*j+i*7]==0) s[i*8*j+i*7]=4;
    }
    while(scanf("%d",&n)!=EOF && n){
        if(s[n]){
            printf("%d\n",s[n]);
            continue;
        }
        puts("3");
    }
}