Algoogle

Algorithm for Programming Contest

JOI 春合宿 2007 Factorial

Category: JOI Tag: math

Fctorial

問題概要


入力としてnが与えられる.
このnで割り切れる最小の値mを求めよ.

解法


nを素因数分解する. 素因数分解はまでの各値で順に割り切れる限り割る. 最後に残った数は1より大きければ素数. 割った回数を保存しておけば素因数分解ができる.

必要な素数とその個数が出たので, その個数分その素数pを用意するために必要な個数を満たすまでpにpを足していく.
これでできた数のmaxが答え.

コード


(Factorial.cpp) download
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n;
vector<pii> p;

void gen_p()
{
        int nn = n;
        for (int i = 2; i < sqrt(n)+1; i++) {
                int k = 0;
                while(nn%i==0) {
                        ++k;
                        nn /= i;
                }
                if(k) p.push_back(pii(i,k));
        }
        if(nn > 1) p.push_back(pii(nn,1));
}

int solve()
{
        gen_p();
        int ans = 0;
        for(auto &e: p) {
                int q = e.first, k = e.second, tmp = 0;
                while(k > 0) {
                        tmp += q;
                        int t = tmp;
                        while(t%q==0) {
                                t /= q;
                                k--;
                        }
                }
                ans = max(ans, tmp);
        }

        return ans;
}

void input()
{
        cin >> n;
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments