lightoj1035

maksyuki 发表于 oj 分类，标签: 数论-素因子分解

27 8月 2015

1035 - Intelligent Factorial Factorization

Input

Given an integer N, you have to prime factorize N! (factorial N).

Input starts with an integer T (≤ 125), denoting the number of test cases.

Each case contains an integer N (2 ≤ N ≤ 100).

Output

For each case, print the case number and the factorization of the factorial in the following format as given in samples.

Case x: N = p₁ (power of p₁) * p₂ (power of p₂) * ...

Here x is the case number, p₁, p₂ ... are primes in ascending order.

Sample Input	Output for Sample Input
3236	Case 1: 2 = 2 (1)Case 2: 3 = 2 (1) * 3 (1)Case 3: 6 = 2 (4) * 3 (2) * 5 (1)

Notes

The output for the 3^rd case is (if we replace space with '.') is

Case.3:.6.=.2.(4).*.3.(2).*.5.(1)

题目类型：素因子分解

算法分析：N!中有素数p的个数为[N/p] + [N/p^2] + [N/p^3] + …由于N不太大，可以先将100以内的素数都打出来，然后从小到大判断每一个素数及其倍数是否满足 N / p ^ k != 0，将结果累加，否则判断下一个素数或者是退出判断

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 100 + 66;

bool prime[maxn];

void GetPrime ()
{
    memset (prime, true, sizeof (prime));

    int i;
    for (i = 2; i < maxn; i++)
    {
        int j;
        for (j = 2; j * i < maxn; j++)
            prime[i*j] = false;
    }
}


int main()
{
//    ifstream cin ("aaa.txt");

    GetPrime ();

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;

        cout << "Case " << flag++ << ": " << n << " = ";

        int i, sum;
        bool is_first = true;

        for (i = 2; i < maxn; i++)
        {
            if (prime[i])
            {
                if (n / i == 0)
                    break;

                sum = n / i;
                int temp = i;
                while (n / (temp * i))
                {
                    sum += n / (temp * i);
                    temp *= i;
                }

                if (is_first)
                {
                    is_first = false;
                    cout << i << " " << "(" << sum << ")";
                }

                else
                    cout << " * " << i << " " << "(" << sum << ")";
            }
        }

        cout << endl;
    }
    
return 0;
}

100

101

102

103

104

105

106

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 100 + 66;

bool prime[maxn];

void GetPrime ()

{

memset (prime, true, sizeof (prime));

int i;

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

{

int j;

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

prime[i*j] = false;

}

int main()

{

// ifstream cin ("aaa.txt");

GetPrime ();

int t, flag = 1;

cin >> t;

while (t--)

{

int n;

cin >> n;

cout << "Case " << flag++ << ": " << n << " = ";

int i, sum;

bool is_first = true;

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

{

if (prime[i])

{

if (n / i == 0)

break;

sum = n / i;

int temp = i;

while (n / (temp * i))

{

sum += n / (temp * i);

temp *= i;

}

if (is_first)

{

is_first = false;

cout << i << " " << "(" << sum << ")";

}

else

cout << " * " << i << " " << "(" << sum << ")";

}

cout << endl;

}

return 0;

}

lightoj1029

lightoj1040

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

lightoj1035

Input

Output

Sample Input

Output for Sample Input

Notes

分类目录

标签云

书签

近期评论