学步园

为什么完全平方数有奇数个因子？

解一： 

       设m为完全平方数，对m进行质因子分解： m=(p1)^a1×(p2)^a2×…×(pn)^an ;

   易知a1,a2,…,an都是偶数，那么a1+1, a2+1, a3+1,...an+1都是奇数。

   于是平方数A的正约数（即因数）个数(a1+1)(a2+1)……(an+1)是奇数,证毕。

解二：

 
 m可以表示为 m = a*a，那么对于大于a的因子，都有小于a的因子与其对应。而只有a落单。

 
 所以m的因数个数为2k+1是奇数，证毕。

例题： uva
10110 - Light, more light

  code:

//完全平方数的因数个数为奇数个。
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    long long n, m;
    while(cin>>n,n)
    {
        m = (int)sqrt(n + 0.5);
        if(m*m==n) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}
/* TLE
#include <iostream>
#include <cmath>
using namespace std;


bool check(int n)
{
    int m = (int)sqrt(n +0.5);
    int t, res = 1;
    for(int i=2; i<=m; i+=2)
    {
        if(!(n%i))
        {
            t = 1;
            while(n%i==0)
            t++, n /=i;
            res =res*t;
        }
        if(i==2) i--;
    }
    if(n>1) res *=2;
    if(res&1) return true;
    return false;
}
int main()
{
    int n;
    while(cin>>n,n)
    {
        if(check(n)) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}
*/