c++ 筛法思想

1.1求解 [ 1 , n ] [1,n] [1,n] 内每个数的约数的个数的和, n = 1 e 6 n = 1e6 n=1e6

例如:

n = 4 n=4 n=4

d ( 1 ) = 1 , d ( 2 ) = 2 , d ( 3 ) = 2 , d ( 4 ) = 3 , 1 + 2 + 2 + 3 = 8 d(1)=1,d(2)=2,d(3)=2,d(4)=3 , 1+2+2+3=8 d(1)=1,d(2)=2,d(3)=2,d(4)=3,1+2+2+3=8
代码如下：

#include 

using namespace std;

int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        ans+=n/i;
    }
    cout<<ans;
    return 0;
}

1.2 求解 [ 1 , n ] [1,n] [1,n] 内有多少对数 i , j i,j i,j 满足 i i i 是 j j j的约数， n = 1 e 6 n = 1e6 n=1e6

例如:

n = 5 , a n s = 5 n = 5 , ans = 5 n=5,ans=5

n = 6 , a n s = 6 n=6,ans=6 n=6,ans=6
代码如下：

#include 

using namespace std;

int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        ans+=n/i-1;//减掉1 1
    }
    cout<<ans;
    return 0;
}

1.3 给定一个序列 a i a_i ai​ , 有多少对数 a i , a j a_i,a_j ai​,aj​ 成倍数。输出对数,序列长度 n = 2 e 5 n = 2e5 n=2e5, a i ≤ 2 e 5 a_i \leq 2e5 ai​≤2e5 ,保证序列中每个数两两不同

例如:

n = 5 , a = [ 1 , 3 , 6 , 2 ] n = 5 , a = [1,3,6,2] n=5,a=[1,3,6,2]

输出: 5 5 5

解法1：预处理每个数的约数，用每个约数到原数组中找，有就说明可以凑成一对，ans++.

#include 
using namespace std;
const int maxn = 2e5 + 4;
vector<int> d[maxn];
int a[maxn];
int main()
{
    // 预处理出每个数的约数列表 d数组
    for (int i = 1 ; i < maxn ; i++){
        for (int j = i ; j < maxn ; j += i){
            d[j].push_back(i);
        }
    }
    int n;
    cin >> n;
    set<int> s;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        s.insert(a[i]);
    }
    int ans = 0;
    for (int i = 1 ; i <= n ; i++){
        for (auto x : d[a[i]]){
            if (s.count(x)) ans++;
        }
    }
    return 0;
}

解法二：用哈希表先将原数组出现过的记录，再将数组中每个数的倍数在哈希表中判断，如果哈希表中有就说明有一对。

#include 
using namespace std;
const int maxn = 2e5 + 4;
int a[maxn] , bk[maxn];
int main()
{
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        bk[a[i]] = 1;
    }
    int ans = 0;
    for (int i = 1 ; i < maxn ; i++){
        for (int j = i + i; j < maxn ; j += i){            
            ans += bk[j];
        }
    }
    return 0;
}

1.4.除数博弈： 当 n = 2 e 5 n = 2e5 n=2e5 怎么做?

题目链接：https://leetcode.cn/problems/divisor-game/submissions/

解题思路：预处理所有n的约数

代码如下：

class Solution {
public:
    
    bool dp[1005];
    const int maxn=2e5+5;
    vector <int> v[2000005];
    bool divisorGame(int n) {
        for(int i=1;i<=n;i++){
            for(int j=i+i;j<=n;j+=i){
                v[j].push_back(i);
            }
        }
        dp[1]=false;
        dp[2]=true;
        dp[3]=false;
        for(int i=4;i<=n;i++){
            for(auto &x:v[i]){
                if(i-x<0) continue;
                if(dp[i-x]==false){
                    dp[i]=true; 
                    cout<<i<<" "<<dp[i]<<endl;
                    break; 
                }
            }
        }
        return dp[n];
    }
};

1.5 输出 [ 1 , n ] [1,n] [1,n]每个数质因分解后的最小质因子,最大质因子以及不同质因子的个数 , n = 1 e 6 n = 1e6 n=1e6

#include 
using namespace std;
const int maxn = 2e5 + 4;
int mi[maxn]; // mi[i] 代表 i的最小质因子.
int mx[maxn]; // mx[i] 代表 i的最大质因子.
int dif[maxn];// dif[i] 代表 i的不同的质因子个数
int main()
{
    int n;
    cin >> n;
    for (int i = 2 ; i <= n ; i++){
        if (mi[i] == 0){
            // i 是个质数
            mi[i] = i;
            mx[i] = i;
            dif[i] = 1;
            for (int j = i + i ; j <= n ; j += i){
                // 求最大
                mx[j] = i;//最后一次赋的肯定是最大的
                dif[j]++;//j的约数 
                // 求最小
                if (mi[j]) continue;//第一次赋的值肯定是最小的
                mi[j] = i;
            }
        }
    }
    for (int i = 1 ; i <= n ; i++){
        cout << mi[i] << " " << mx[i] << " " << dif[i] << endl;
    }
    return 0;
}