算法进阶-数论进阶

High2

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<vector>
using namespace std;

int main() {
    int T;
    cin>>T;
    while(T--){
        string N;
        cin>>N;
        long long n=stoll(N);
        int can=0;
        for(auto ch:N){
            int dight=ch-'0';
            if(dight==0||n%dight==0){ //主要条件，不用去重
                can++;
            }
        }
        if(can==N.size()){
            cout<<"G\n";
        }else if(can==0){
            cout<<"S\n";
        }else{
            cout<<"H\n";
        }
        

    }
}
// 64 位输出请用 printf("%lld")

High3

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz size()
#define vll vector<long long>
using ll=long long;
using ull = unsigned long long;
const int MOD1=1e9+7;
const int MOD2=998244353;
void solve() {
    //HIGH3 阶乘末尾非零数字
    int n;
    cin>>n;
    unsigned long long now = 1;
    for (int i=2;i<=n;i++) {
        now*=i;
        while (now%10==0) now/=10;//注意这里不能是if，可能一次相乘产生不止一个0
        now%=10000000;
    }
    cout<<now%10;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;
    while (t--) {
        solve();
    }
}

High4

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz size()
#define vll vector<long long>
using ll=long long;
using ull = unsigned long long;
const int MOD1=1e9+7;
const int MOD2=998244353;
void solve() {
    //HIGH3 分解质因数
    //https://www.nowcoder.com/practice/35723516d6f841ca8869ecbcf3ddacaf
    vector<ll> ans;
    long long n;
    cin>>n;
    for(int i=2;i*i<=n;i++) {
        while (!(n%i)) {
            cout<<i<<" ";
            n/=i;
        }
    }
    if(n!=1) cout<<n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;
    while (t--) {
        solve();
    }
}

High5

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz size()
#define vll vector<long long>
using ll=long long;
using ull = unsigned long long;
const int MOD1=1e9+7;
const int MOD2=998244353;
void solve() {
    //HIGH5 小红和小紫的取素因子游戏
    //https://www.nowcoder.com/practice/6146f391a69547c4804fe8d0330f1745
    int ansconut=0;
    long long n;
    cin>>n;
    for(int i=2;i*i<=n;i++) {
        while (!(n%i)) {
            ansconut++;
            n/=i;
        }
    }
    if(n!=1) ansconut++;
    if (n%2==0)cout<<"yukari\n";
    else cout<<"kou\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    cin>>t;
    while (t--) {
        solve();
    }
}

High6

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz size()
#define vll vector<long long>
using ll=long long;
using ull = unsigned long long;
const int MOD1=1e9+7;
const int MOD2=998244353;
void solve() {
    //HIGH6最小乘积代价和
    //https://www.nowcoder.com/practice/0096a5fa8a344a099be103e2d9395cc4
    //相当简单的能推出，只要因数拆成最小，答案一定最小
    ll ans=0;
    ll n;
    cin>>n;
    for(int i=2;i*i<=n;i++) {
        while (!(n%i)) {
            ans+=i;
            n/=i;
        }
    }
    if(n!=1) ans+=n;
    cout<<ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;
    while (t--) {
        solve();
    }
}

High7

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz size()
#define vll vector<long long>
using ll=long long;
using ull = unsigned long long;
const int MOD1=1e9+7;
const int MOD2=998244353;
void solve() {
    //HIGH7 小苯的数字权值
    //https://www.nowcoder.com/practice/aeacca655eec45999a6dc4d998dfd4a5
    //数论知识：一个数的正因子数=各个因子数量+1互乘
    //n = p1^e1 × p2^e2 × ... × pk^ek，那么n的因子个数 = (e1+1)(e2+1)...(ek+1)
    ll split=0;
    ll nosplit=1;
    ll n;
    cin>>n;
    for(int i=2;i*i<=n;i++) {
        ll count=0;//用来数这个因子的数量的
        while (!(n%i)) {
            split+=2;
            count++;
            n/=i;
        }
        nosplit*=(count+1);
    }
    if(n!=1) {
        split+=2;
        nosplit*=2;
    }
    cout<<max(nosplit,split)<<'\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    cin>>t;
    while (t--) {
        solve();
    }
}

High8 筛法判断质数

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b) { return (a + b) % MOD; }
inline ll submod(ll a, ll b) { return (a - b + MOD) % MOD; }
inline ll mulmod(ll a, ll b) { return a * b % MOD; }

//HIGH8 筛法判断质数
//https://www.nowcoder.com/practice/8afab457ef11456d8602ce6dc30db776

//埃氏筛舒适区内
void Eratosthenes(int n,vector<int> &primes,vector<bool> &isPrime) {
    //埃拉托斯特尼筛法（埃氏筛）
    //传参前保证数组大小大于n+1！
    //primes返回小于n的所有质数！
    isPrime[0]=isPrime[1]=false;
    for (int i=2; i<n; i++) isPrime[i] = true;
    for(int i=2;i*i<=n;i++) {
        if(isPrime[i]) {
            primes.push_back(i);
            for(int j=i*i;j<=n;j+=i) {
                isPrime[j]=false;
            }
        }
    }
}
void solve() {
    vector<int> primes(1e6+1);
    vector<bool> isPrime(1e6+1);
    Eratosthenes(1e6,primes,isPrime);
    int T;
    cin>>T;
    while(T--) {
        int n;
        cin>>n;
        if (isPrime[n]) {
            cout<<"Yes"<<'\n';
        }else {
            cout<<"No"<<'\n';
        }
    }


}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High9 质数统计

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b) { return (a + b) % MOD; }
inline ll submod(ll a, ll b) { return (a - b + MOD) % MOD; }
inline ll mulmod(ll a, ll b) { return a * b % MOD; }

//HIGH9 质数统计
//https://www.nowcoder.com/practice/d832b0c1a0bd4394a3229f06c6f0b50b

//埃氏筛或者欧拉筛加上前缀和全出来了
void Eratosthenes(int n,vector<int> &primes,vector<bool> &isPrime) {
    //埃拉托斯特尼筛法（埃氏筛）
    //传参前保证数组大小大于n+1！
    //primes返回小于n的所有质数！
    isPrime[0]=isPrime[1]=false;
    for (int i=2; i<n; i++) isPrime[i] = true;
    for(int i=2;i*i<=n;i++) {
        if(isPrime[i]) {
            primes.push_back(i);
            for(int j=i*i;j<=n;j+=i) {
                isPrime[j]=false;
            }
        }
    }
}
void solve() {
    vector<int> primes(1e6+1);
    vector<bool> isPrime(1e6+1);
    Eratosthenes(1e6,primes,isPrime);
    vector<int> qzh(1e6+1,0);
    for(int i=1;i<=1e6;i++) {
        qzh[i]=qzh[i-1]+(isPrime[i]==true?1:0);
    }
    int T;
    cin>>T;
    while(T--) {
        int l,r;
        cin>>l>>r;
        cout<<qzh[r]-qzh[l];
    }


}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High10 素数对

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b) { return (a + b) % MOD; }
inline ll submod(ll a, ll b) { return (a - b + MOD) % MOD; }
inline ll mulmod(ll a, ll b) { return a * b % MOD; }

//HIGH10 素数对
//https://www.nowcoder.com/practice/9aaa288943e7498a9626d4f4f12ced4c

//应该是先埃氏筛计算出所有的质数，再暴力计算答案
//虽然暴力可行但是通过计算有更好解法
//通过分析，质数中唯一一个偶数是2，假设A和B没有偶数（2），则加和得到的数一定是偶数，所以C也必须是整数
//又因为C是质数，所以这种情况只有可能C为2，C^2=4，没有一组素数成立，所以不可能A和B都是奇质数
//所以在AB里至少有一个是2，或者ABC都是2
//AB设一个为2再枚举C即可
void Eratosthenes(int n,vector<int> &primes,vector<bool> &isPrime) {
    isPrime[0]=isPrime[1]=false;
    for (int i=2; i<n; i++) isPrime[i] = true;
    for(int i=2;i*i<=n;i++) {
        if(isPrime[i]) {
            primes.push_back(i);
            for(int j=i*i;j<=n;j+=i) {
                isPrime[j]=false;
            }
        }
    }
}

void solve() {
    vector<int> primes;
    vector<bool> isPrime(1e6+1);
    Eratosthenes(1e6,primes,isPrime);
    vector<int> qzh(1e6+1,0);
    int N;
    cin>>N;
    ll ans=0;
    for (ll C=2;C<=N;C++) {
        if (isPrime[C]) {//前提是C是质数
            ll AB=(ll)C*C-2; //计算A/B
            if (AB>N) break;//超过N跳出
            if (AB>0&&isPrime[AB]) {//A/B得是正质数
                ans+=(AB==2?1:2);//特判2
            }
        }
    }
    cout<<ans;


}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}