HDU 4196 Remoteland

题意：给定一个n,然后让你从1-n中选出某些数乘起来，使得乘积最大，并且乘积必须是完全平方数。

思路：将1-n种每个数都分解素因子，把他们的素因子的幂加起来，如果是偶数，就说明可以构成完全平方数，乘起来，如果是奇数，说明不能构成，减去一个就是偶数了，所以减去一个再乘起来。因为要分解1-n当中所有的素因子，然后乘起来，那么也就是分解n!的素因子，所以只要找出来他的所有的素因子的幂指数为奇数的直接除就行了。现在有个问题是不能除。要取模，更好的方法是，再算n!的时候，不乘素数，那样的话，就到最后再乘。如果是奇次幂，就不用乘，偶次幂再乘。这样的话，就需要找出1-n当中素因子是多少次幂，方法是，直接用n除以素因子，然后加起来，知道n为0。具体见代码。

吐嘈：这个题意完全读不懂啊。。。看了题解才知道的。还有就是这种方法太奇妙了。赞赞赞！

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = ;

const ll mod = 1000000007LL;

const int sqrtmaxn = (int)(sqrt((double)maxn));

ll fac[maxn];

int prime[maxn];

int cnt;

void init()

{

    memset(prime, , sizeof(prime));

    fac[] = fac[] = ;//阶乘

    cnt = ;

    for (int i = ; i < maxn; i++)

    {

        fac[i] = fac[i - ];

        if (prime[i] == )//如果是素数，就先不乘

        {

            prime[cnt++] = i;

            if (i <= sqrtmaxn)

                for (int j = i * i; j < maxn; j += i)

                    prime[j] = ;

        }

        else fac[i] = (fac[i] * i) % mod;//不是素数直接乘

    }

}

int main()

{

    init();

    int n;

    while (~scanf("%d", &n) && n)

    {

        ll ans = fac[n];

        for (int i = ; i < cnt && prime[i] <= n; i++)

        {

            int tot = , tmp = n;//tmp统计素因子的幂次

            while (tmp) tot += (tmp /= prime[i]);

            if ((tot & ) == ) ans = (ans * prime[i]) % mod;

        }

        printf("%d\n", (int)ans);

    }

    return ;

}