csu 1801(合数分解+排列组合)

1801: Mr. S’s Romance

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 15 Solved: 5
[Submit][Status][Web Board]

Description

Mr.
S is a young math professor who is famous for being crazy about
collecting prime numbers. Once he met a number, he would first divide it
into several prime numbers and then push them into his magic box. Every
week, Mr. S sell out the primes in his box to earn money.

Today is August 22th, which is an important day to Mr. S because it’s his girl friend’s
birthday. She is a perfect girl, so Mr. S decide to choose some numbers
from his magic box to multiply to form a perfect square number as a
love present.Undoubtedly, he must pick up one number.

This
week, Mr. S has totally met n numbers a1,a2,...,an. Suddenly, Mr.S come
up with an exciting question that how many different ways of choices
can form a perfect square number as a present. Can you help him solve
it? The answer maybe too large, so you should output the answer modulo
by 1000000007.

Input

First line is a positive integer T (<=5), represents there are T test cases.

For each test case:

First line includes a number n(1≤n≤100000)，next line there are n numbers a1,a2,...,an,(1<ai≤10^6).

Output

For the i-th test case , first output Case #i: in a single line.

Then output the answer of i-th test case modulo by 1000000007.

Sample Input

Sample Output

Case #1:

3

Case #2:

3

题意:在 n 个整数的质因子的里面选若干个组成完全平方数的种类数?
题解:把各个数分解得到质因子数 ,然后要是完全平方数,那么每种质因子的个数都要是偶数,对于某个质因子假设个数为 x,那么选法就有 C(x,0)+C(x,2)+..+C(x,最接近x的那个偶数) = 2^(x-1) 通过排列组合得解.

答案要减掉全部都不选的那种.

#include <iostream>

#include <cstring>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

using namespace std;

typedef long long LL;

const LL mod = ;

const int N = ;

int n;

LL prime[N+];

LL num[N];

void getPrime()

{

    memset(prime,,sizeof(prime));

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

    {

        if(!prime[i])prime[++prime[]]=i;

        for(int j=; j<=prime[]&&prime[j]<=N/i; j++)

        {

            prime[prime[j]*i]=;

            if(i%prime[j]==) break;

        }

    }

}

LL fatCnt;

void getFactors(LL x)

{

    LL tmp=x;

    for(int i=; prime[i]<=tmp/prime[i]; i++)

    {

        if(tmp%prime[i]==)

        {

            while(tmp%prime[i]==)

            {

                num[prime[i]]++;

                tmp/=prime[i];

            }

        }

    }

    if(tmp!=) num[tmp]++;

}

LL pow_mod(LL a,LL n){

    LL ans = ;

    while(n){

        if(n&) ans = ans*a%mod;

        a = a*a%mod;

        n>>=;

    }

    return ans;

}

int main()

{

    int tcase,t=;

    scanf("%d",&tcase);

    getPrime();

    while(tcase--)

    {

        memset(num,,sizeof(num));

        int n;

        scanf("%d",&n);

        LL a;

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

        {

            scanf("%lld",&a);

            getFactors(a);

        }

        LL ans = ;

        for(int i=;i<N;i++){

            if(num[i]>){

                ans = ans*pow_mod(,num[i]-)%mod;

            }

        }

        printf("Case #%d:\n%lld\n",t++,ans-);

    }

    return ;

}

巴特西