洛谷10月月赛R1·浴谷八连测R1·提高组 SAC E#1 – 一道中档题 Factorial

洛谷题号:3927
这个代码迭代了四个版本;;;
贴上来四个代码,最后再顺便上传一个代码+题解的压缩包;

Ver1:

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#include<cstring>
#include<cassert>
using namespace std;
#define ull unsigned long long
int main(){
    ios::sync_with_stdio(false);
    ull n, k;
    cin >> n >> k;
    ull re = 1, cnt = 0;
    for (ull i = 1; i <= n; i++){
        ull t = i;
        while (t%k == 0){
            t /= k;
            cnt++;
        }
        re *= t;
        while (re%k == 0){
            re /= k;
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Ver2:

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
#define ull unsigned long long
map<ull, ull> prime_cnt_ori;
map<ull, ull> prime_cnt;
ull n, k;
void breakdown_prime(ull k){//将k进行质因数分解,在map中存储每一个质因数
    for (ull i = 2; i <= k; i++){
        while (k%i == 0){
            prime_cnt_ori[i]++;
            k /= i;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k;
    breakdown_prime(k);
    for (ull i = 1; i <= n; i++){
        ull t = i;
        for (map <ull, ull>::iterator iter = prime_cnt_ori.begin(); iter != prime_cnt_ori.end(); iter++){
            while (t % (*iter).first == 0){
                t /= (*iter).first;
                prime_cnt[(*iter).first]++;
            }
        }
    }
    ull mmin = 1e8;
    for (map<ull, ull>::iterator iter = prime_cnt_ori.begin(); iter != prime_cnt_ori.end(); iter++){
        ull t = prime_cnt[(*iter).first] / (*iter).second;
        mmin = min(t, mmin);
    }
    cout << mmin << endl;
    return 0;
}

Ver3:

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
#define ull unsigned long long
struct prime{
    ull number;
    ull cnt;
}prime_cnt_ori[1000000], prime_cnt[1000000];
ull n, k;
ull prime_cnter=0;
void breakdown_prime(ull k){//将k进行质因数分解,在数组中存储每一个质因数
    for (ull i = 2; i <= k; i++){
        if (k%i == 0){
            prime_cnter++;
            prime_cnt_ori[prime_cnter].number = i;
            prime_cnt_ori[prime_cnter].cnt = 0;
            while (k%i == 0){
                prime_cnt_ori[prime_cnter].cnt++;
                k /= i;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k;
    breakdown_prime(k);
    for (ull i = 1; i <= n; i++){
        ull t = i;
        for (int i = 1; i <= prime_cnter;i++){
            while (t % prime_cnt_ori[i].number == 0){
                t /= prime_cnt_ori[i].number;
                prime_cnt[i].cnt++;
            }
        }
    }
    ull mmin = 1e8;
    for (int i = 1; i <= prime_cnter; i++){
        ull t = prime_cnt[i].cnt / prime_cnt_ori[i].cnt;
        mmin = min(t, mmin);
    }
    cout << mmin << endl;
    return 0;
}

Ver4:(AC)

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
#define ull unsigned long long
ull prime[1000000], prime_cnt_ori[1000000], prime_cnt[1000000];
ull n, k;
ull prime_cnter = 0;
void breakdown_prime(ull k){//将k进行质因数分解,存储每一个质因数
    for (ull i = 2; i <= k; i++){
        if (k%i == 0){
            prime_cnter++;
            prime[prime_cnter] = i;
            prime_cnt_ori[prime_cnter] = 0;
            while (k%i == 0){
                prime_cnt_ori[prime_cnter]++;
                k /= i;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k;
    breakdown_prime(k);
    for (int i = 1; i <= prime_cnter; i++){
        prime_cnt[i] = 0;
        ull t = prime[i];
        while (n / t){
            prime_cnt[i] += n / t;
            t *= prime[i];
        }
    }
    ull mmin=1e18;
    for (int i = 1; i <= prime_cnter; i++){
        ull t = prime_cnt[i] / prime_cnt_ori[i];
        mmin = min(t, mmin);
    }
    cout << mmin << endl;
    return 0;
}

最后是代码压缩包+题解:
luogu-p3927.zip

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注