【牛客練習賽8】A D E

A 約數個數的和

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 32768K，其他語言65536K

64bit IO Format: %lld

題目描述

給個n，求1到n的所有數的約數個數的和~

輸入描述:

第一行一個正整數n

輸出描述:

輸出一個整數，表示答案

示例1

輸入

3

輸出

5

說明

樣例解釋：

1有1個約數1

2有2個約數1,2

3有2個約數1,3

備注:

n <= 100000000

分析： 枚舉因子，看1-n中有幾個數是有這個因子的。

代碼

//package FirstTime;
import java.util.*;
import java.math.*;
import java.text.DecimalFormat;

public class Main{
    static final int MAXN = +;
    static final int MAXM = +;
    static final int inf = ;

    public static void main(String[] agrs){
        Scanner cin = new Scanner(System.in);
        int n;
        while(cin.hasNext()){
            n=cin.nextInt();
            long ans=;int i;
            for(  i=;i*i<=n;i++){
                ans+=n/i;
            }
            ans+=(n-i+);
            System.out.println(ans);
        }


    }
}
           

B 儲物點的距離

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 131072K，其他語言262144K

64bit IO Format: %lld

題目描述

一個數軸，每一個儲物點會有一些東西，同時它們之間存在距離。

每次給個區間[l,r],查詢把這個區間内所有儲物點的東西運到另外一個儲物點的代價是多少？

比如儲物點i有x個東西，要運到儲物點j，代價為x * dist( i , j )

dist就是儲物點間的距離。

輸入描述:

第一行兩個數表示n,m

第二行n-1個數，第i個數表示第i個儲物點與第i+1個儲物點的距離ai

第三行n個數，表示每個儲物點的東西個數bi

之後m行每行三個數x l r

表示查詢要把區間[l,r]儲物點的物品全部運到儲物點x的花費

每次查詢獨立

輸出描述:

對于每個詢問輸出一個數表示答案

答案對1000000007取模

示例1

輸入

5 5

2 3 4 5

1 2 3 4 5

1 1 5

3 1 5

2 3 3

3 3 3

1 5 5

輸出

125

72

9

70

備注:

對于100%的資料n,m <= 200000 , 0 <= ai,bi <= 2000000000

分析： 打出字首表，好吧，我代碼bug調半天還沒有調出來（看别人正确代碼，打的表一樣的啊，但是好像最後查詢處 計算的方法不太一樣，可能錯這裡了）還要補作業 ，晚點再貼吧，QAQ 。

D 加邊的無向圖

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 32768K，其他語言65536K

64bit IO Format: %lld

題目描述

給你一個 n 個點，m 條邊的無向圖，求至少要在這個的基礎上加多少條無向邊使得任意兩個點可達~

輸入描述:

第一行兩個正整數 n 和 m 。

接下來的m行中，每行兩個正整數 i 、 j ，表示點i與點j之間有一條無向道路。

輸出描述:

輸出一個整數，表示答案

示例1

輸入

4 2

1 2

3 4

輸出

1

備注:

對于100%的資料，有n,m<=100000。

分析：看有幾顆樹就行了 。dfs掃一遍。

#include<bits/stdc++.h>
using namespace std;

const int MAXN = +;
const int MAXM = ;
const int mod = +;
const int inf = ;

bool vis[MAXN+];
vector<int>ve[MAXN+];
int n,m;
int ans;
void init(){
    for(int i=;i<=n;i++) ve[i].clear();
    memset(vis,,sizeof(vis));
}
void dfs(int now,int pre){
    vis[now]=;
    for(int i=;i<ve[now].size();i++){
        int v=ve[now][i];
        if(vis[v]||v==pre) continue;
        dfs(v,now);
    }
}
int main(){

    scanf("%d%d",&n,&m);
    init();
    while(m--){
        int a,b;scanf("%d%d",&a,&b);
        ve[a].push_back(b);
        ve[b].push_back(a);
    }
    ans=;
    for(int i=;i<=n;i++){
        if(!vis[i]) {
             ans++;
             dfs(i,-);
        }
    }
    printf("%d\n",ans-);
    return ;
}
           

E 集合中的質數

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 32768K，其他語言65536K

64bit IO Format: %lld

題目描述

給出一個集合和一個數m。

集合裡面有n個質數。

請你求出從 1 到 m 的所有數中，至少能被集合中的一個數整除的數的個數。

輸入描述:

第一行兩個正整數 n 和 m 。

第二行n個正整數，分别為集合中的質數。

輸出描述:

輸出一個整數，表示符合要求的正整數的個數。

示例1

輸入

3 37

5 7 13

輸出

13

備注:

對于100%的資料，有n<=20，m為有符号64位正整數，集合内質數<=1000000000

分析：容斥裸題，這裡用的狀态壓縮枚舉所有狀态。

有一點就是這個LCM的時候可能會爆LL，就改了一點，當時想着要是還是爆LL ，就要上java了，但是這樣就可以過了。

#include<bits/stdc++.h>
using namespace std;
#define LL long long

const int MAXN = ;
const int MAXM = ;
const int mod = +;
const int inf = ;

LL a[MAXN];
int main(){

    LL n,m;
    while(scanf("%lld%lld",&m,&n)!=EOF){
        for(int i=;i<m;i++) scanf("%lld",&a[i]);
        LL ans=;
        for(int i=;i<(<<m);i++){  //
            int cnt=;  LL LCM = ;  int flag=;
            for(int j=;j<m;j++){
                if(&(i>>j)) {
                    if(LCM>n) { // 可以直接逃過
                        flag=;
                        break;
                    }
                    cnt++;
                    LCM= LCM*a[j];
                 }
             }
             if(flag) continue;
             if(cnt&) ans+=n/LCM;
             else ans-=n/LCM;
         }
         printf("%lld\n",ans);
     }
}