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< 
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< 
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 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 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  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< 
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;
}