우 객 연습 경기 8 (1 ~ n 약수 와) (접두사 와 좋 은 문제) (가 변 연통 도) (용 척 원리)

제목 설명
n 을 주 고 1 부터 n 까지 의 모든 수의 약수 와 ~
입력 설명:

        n

출력 설명:

      ，    

예시 1
입력

3

출력

5

설명 하 다.

    ：
1 1   1
2 2   1,2
3 2   1,3

비고:

n <= 100000000

#include

int deal(int n)
{
    int ans=0;
    for(int i=1;i<=n;i++)
        ans+=n/i;
    return ans;
}
int main()
{
    int n;
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
        printf("%d
",deal(n));
    return 0;
}

B
제목 설명
 하나의 축 은 모든 저장 점 에 약간의 물건 이 있 을 뿐만 아니 라, 동시에 그것들 사이 에 거리 가 존재 한다.
매번 한 구간 [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
0
70
  
비고:
 
   
对于100%的数据n,m <= 200000 , 0 <= ai,bi <= 2000000000
 
  

思路：

计算所有点到点1的距离以及前缀和，然后根据关系计算得到答案即可

另一种思路：计算前面所有点到 i 的权值和，但是不知道为什么一直错，找不到原因了

#include
#include
#include
using namespace std;

#define MAXN 200005
#define LL long long
#define mod 1000000007

int n,m;
LL a[MAXN],b[MAXN],s[MAXN];

void init(){
    for(int i=2;i<=n;i++)
            scanf("%lld",&a[i]),a[i]=(a[i]+a[i-1])%mod;
    for(int i=1;i<=n;i++)
        scanf("%lld",&b[i]),s[i]=(s[i-1]+a[i]*b[i])%mod,b[i]=(b[i]+b[i-1])%mod;
}

LL get_left(int l,int r,int x){
    return a[x]*(b[r]-b[l-1])-(s[r]-s[l-1]);
}
LL get_right(int l,int r,int x){
    return s[r]-s[l-1]-a[x]*(b[r]-b[l-1]);
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        while(m--)
        {
            int x,l,r;
            scanf("%d%d%d",&x,&l,&r);
            LL ans=0;
            if(x>=r)      ans=get_left(l,r,x);
            else if(x<=l) ans=get_right(l,r,x);
            else ans=get_left(l,x,x)+get_right(x,r,x);
            printf("%lld
",(ans%mod+mod)%mod);
        }
    }
    return 0;
}

D
제목 설명
하나 줄 게. n 시, m 한 변 의 무 방향 도 는 적어도 이것 을 바탕 으로 몇 개의 무 방향 변 을 더 해서 임의의 두 점 을 도달 할 수 있 도록 해 야 합 니까? 
입력 설명:

         n   m 。
    m  ，        i 、 j ，   i  j         。

출력 설명:

      ，    

예시 1
입력

4 2
1 2
3 4

출력

1

비고:

  100%   ， n,m<=100000。

연결 블록 에 ans 개가 있 으 면 ans - 1 을 출력 하면 됩 니 다.
dfs, bfs 를 이용 하여 구 할 수 있 습 니 다.

#include
#include
#include
using namespace std;

#define MAXN 100005
int father[MAXN],visit[MAXN];
int find_it(int x){
    int tempx=x,t;
    while(tempx!=father[tempx])
        tempx=father[tempx];
    while(father[x]!=x){
        t=father[x];
        father[x]=tempx;
        x=t;
    }
    return tempx;
}
void unite(int num1,int num2){
    int tx=find_it(num1);
    int ty=find_it(num2);
    if(tx!=ty)
        father[tx]=ty;
}

int main()
{
    int n,m,a,b;
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<=n;i++)
            father[i]=i;
        for(int i=0;i

E
제목 설명
집합 하나 와 수 m 를 제시 하 다.
집합 안에 n 개의 소수 가 있다.
제발 1 도착 하 다 m 의 모든 수 중에서 적어도 집합 중의 한 수 에 의 해 정 제 될 수 있 는 수의 개수.
입력 설명:

         n   m 。
   n    ，         。

출력 설명:

      ，             。

예시 1
입력

3 37
5 7 13

출력

13

비고:

  100%   ， n<=20，m    64    ，     <=1000000000

용 척 원리 처리
여기 서 n 개의 수 는 모두 질 수 이 므 로 우 리 는 직접 두 개의 수 를 곱 하여 최대 공약 수 를 얻 을 수 있 습 니 다. 만약 에 질 수 를 보장 하지 못 하면 최대 공약 수 를 요구 합 니 다.
왜냐하면 18 / 6 + 18 / 9.  - 18 / lcm (6, 9) 정 답 이 맞습니다.

#include
#include
#include
using namespace std;

#define LL long long
LL a[100];
LL n,m,ans;

LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}
LL lcm(LL a,LL b)
{
    return a*b/gcd(a,b);
}

void dfs(int now,LL num,int sym)
{
    if(num)  ans+=m/num*sym;
    for(int i=now+1;i<=n;i++)
        dfs(i,lcm(num,a[i]),-1*sym);
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        ans=0;
        for(int i=1;i<=n;i++)
            dfs(i,a[i],1);
        printf("%lld
",ans);
    }
    return 0;
}