2013年9月30日 星期一

2013/9/30 TIOJ 1349 [特別加考題] 平方國的平方幣

// http://218.210.35.237:8080/JudgeOnline/showproblem?problem_id=1349
/*
      數學題阿.... 冏....

      截自 http://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%95%B0
      四平方和定理說明所有正整數均可表示為最多四個平方數的和。特別的,三個平方數之和不能         表示形如 4k(8m + 7) 的數。若一個正整數可以表示因數中沒有形如 4k + 3 的素數的奇次方,則       它可以表示成兩個平方數之和。
 */
#include <iostream>
#include <cstdio>

using namespace std;

int ans[10000001];

int main()
{
    for(int i = 1; i*i <= 10000000; i++){ ans[i*i] = 1; }

    for(int i = 1; i*i <= 10000000; i++)
        for(int j = 1; j*j + i*i <= 10000000; j++)
            if( !ans[i*i+j*j] )
                ans[i*i+j*j] = 2;

    for(int i = 1; i <= 10000000; i++)
        if( !ans[i] )
        {
            int t = i;
            while( t%4 == 0 )
                t/=4;
            if( t%8 == 7 )
                ans[i] = 4;
            else
                ans[i] = 3;
        }

    int n;
    while( scanf("%d", &n) )
    {
        if( n == 0 )
            break;

        printf("%d\n", ans[n]);
    }
    return 0;
}

沒有留言:

張貼留言