专栏首页AI那点小事CCF考试——201709-5除法

CCF考试——201709-5除法

概要

问题描述

  小葱喜欢除法,所以他给了你N个数a1, a2, ⋯, aN,并且希望你执行M次操作,每次操作可能有以下两种:   给你三个数l, r, v,你需要将al, al+1, ⋯, ar之间所有v的倍数除以v。   给你两个数l, r,你需要回答al + al+1 + ⋯ + ar的值是多少。

输入格式

  第一行两个整数N, M,代表数的个数和操作的次数。   接下来一行N个整数,代表N个数一开始的值。   接下来M行,每行代表依次操作。每行开始有一个整数opt。如果opt=1,那么接下来有三个数l, r, v,代表这次操作需要将第l个数到第r个数中v的倍数除以v;如果opt = 2,那么接下来有两个数l, r,代表你需要回答第l个数到第r个数的和。

输出格式

  对于每一次的第二种操作,输出一行代表这次操作所询问的值。

样例输入

5 3 1 2 3 4 5 2 1 5 1 1 3 2 2 1 5

样例输出

15 14

评测用例规模与约定

  对于30%的评测用例,1 ≤ N, M ≤ 1000;   对于另外20%的评测用例,第一种操作中一定有l = r;   对于另外20%的评测用例,第一种操作中一定有l = 1 , r = N;   对于100%的评测用例,1 ≤ N, M ≤ 105,0 ≤ a1, a2, ⋯, aN ≤ 106, 1 ≤ v ≤ 106, 1 ≤ l ≤ r ≤ N。


思路 典型在线处理的思路,注意数据类型用long long,不然数大了会溢出。但是还是超时了。


代码

#include <cstdio>
#include <iostream>
using namespace std;

long long data[100001];
long long N,M;
int opt;
long long i,l,r,v,sum;

void Sub(long long l ,long long r,long long v)
{
    for(i = l ; i <= r ; i++){
        if(data[i] % v == 0){
            data[i] /= v;
        }
    }
}

void Sum(long long l ,long long r)
{
    sum = 0;
    for(i = l ; i <= r ; i++){
        sum += data[i];
    }
 } 

int main()
{
    scanf("%lld %lld",&N,&M); 
    for(i = 1 ; i <= N ; i++){
        scanf("%lld",&data[i]);
    }
    for(i = 0 ; i < M ; i++){
        scanf("%d ",&opt);
        if(opt == 1){
            scanf("%lld %lld %lld",&l,&r,&v);
            Sub(l,r,v);
        }else{
            scanf("%lld %lld",&l,&r);
            Sum(l,r);
            cout<<sum<<endl;
        }
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • CCF考试——201703-3地铁修建

      A市有n个交通枢纽,其中1号和n号非常重要,为了加强运输能力,A市决定在1号到n号枢纽间修建一条地铁。   地铁由很多段隧道组成,每段隧道连接两个交通...

    AI那点小事
  • 剑指offer——对称的二叉树

    题目描述 请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

    AI那点小事
  • 开门人和关门人

    题目描述 每天第一个到机房的人要把门打开,最后一个离开的人要把门关好。现有一堆杂乱的机房签到、签离记录,请根据记录找出当天开门和关门的人。 输入...

    AI那点小事
  • 统计页码数字0~9分别出现了多少次

    最简单的方法是依次遍历每个数字,但这种算法时间复杂度太高,若再用上递归,数字一大内存就爆了,时空复杂度都很高,令人无法忍受。

    xiaoxi666
  • 1034 有理数四则运算 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 关于byte[]字节传输的大端和小端小议

    当前的存储器,多以byte为访问的最小单元,当一个逻辑上的地址必须分割为物理上的若干单元时就存在了先放谁后放谁的问题,于是端(endian)的问题应运而生了,对...

    Gxjun
  • Java工具集-分布式全局唯一ID生成

    cwl_java
  • Java四类八种基本数据类型进一步了解Java

    Java字符采用Unicode编码,每个字符占两个字节,因而可用16进制编码形式表示

    java架构师
  • ORB-SLAM中四叉树管理角点

    四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,如此递归下去,直至树的层次达到一定深度或者满足某种要求后停...

    点云PCL博主
  • Linux系统中对ipmi 配置管理(远程管理卡工具)

    2019年6月19日 ⋅ 浏览量: 3    ...

    以谁为师

扫码关注云+社区

领取腾讯云代金券