ACdream 1070 神奇的%系列二 (数学+二分)

以你之姓@ 2022-06-13 14:20 256阅读 0赞

题目链接：  
[ACdream 1070][]

题解:  
直接用lower\_bound()和upper\_bound()去二分。

AC代码：

/*
    * this code is made by LzyRapx
    * Problem: 1070
    * Verdict: Accepted
    * Submission Date: 2017-07-09 13:15:09
    * Time: 2508MS
    * Memory: 8264KB
    */
    #include<bits/stdc++.h>
    using namespace std;
    const int N=123456;
    int n,q;
    vector<int>p[N];
    int solve(int l,int r,int k)
    {
        return upper_bound(p[k].begin(),p[k].end(),r) - lower_bound(p[k].begin(),p[k].end(),l);
    } 
    int main()
    {
        while(~scanf("%d",&n))
        {
            for(int i=1;i<N;i++){
                p[i].clear();
            }
            int x;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&x);
                p[x].push_back(i);
            }
            scanf("%d",&q);
            int l,r,w;
            for(int i=0;i<q;i++)
            {
                scanf("%d %d %d",&l,&r,&w);
                int sum = 0;
                for(int j=1;j*j<=w;j++)
                {
                    if(w%j==0)
                    {
                        sum+=solve(l,r,j);
                        if(j*j!=w)
                        {
                            sum+=solve(l,r,w/j);
                        }
                    }
                }
                printf("%d\n",sum);
            }
         } 
        return 0;
    }

[ACdream 1070]: http://acdream.info/problem?pid=1070

发表评论取消回复

表情：

评论列表（有 0 条评论，256人围观）

还没有评论，来说两句吧...

相关阅读

相关 Trailing Zeroes (III) 数学思维+二分

目链接：https://vjudge.net/problem/POJ-1426 /********* 二分查找 n! 末尾有几个零，其实就是 1～n中有几个...

港控/mmm°/ 2024年04月17日 05:58/ 0 赞/ 133 阅读

相关《神奇的数学》读后感_《神奇的数学》内容

神奇的数学 ![3646000123e7be5bb379c342dd649824.png][] ![27d93946cfc60b27e00a19854a3ebb9b.png

客官°小女子只卖身不卖艺/ 2023年01月10日 03:53/ 0 赞/ 328 阅读

相关数学聊斋之二

数学聊斋之二（李尚志）发信人: mingzi (单身汉) 二、《指鹿为马》之幼儿版 —— 纠错码最近读到一则笑话：某人向客人夸耀自己的儿子博比特别聪明

- 日理万妓/ 2022年09月18日 05:53/ 0 赞/ 192 阅读

相关 ACdream 1089 barty的智商（二分）

题目链接： [ACdream 1089][] 题解：二分。直接二分枚举智商，然后将大于二分出来的智商的边抠出来建一个图，然后直接从入度为 0<script t

骑猪看日落/ 2022年06月14日 12:21/ 0 赞/ 250 阅读

相关 ACdream 1084 寒假安排（数学题）

题目链接： [ACdream 1084][] 题解：就是让你求A(n,m)的K进制下末尾0的个数。 K太大，显然不能直接模。 A(n,m)转换成k进制有多少

喜欢ヅ旅行/ 2022年06月14日 11:50/ 0 赞/ 207 阅读

相关 ACdream 1070 神奇的%系列二 (数学+二分)

题目链接： [ACdream 1070][] 题解: 直接用lower\_bound()和upper\_bound()去二分。 AC代码： /

以你之姓@/ 2022年06月13日 14:20/ 0 赞/ 257 阅读

相关 ACdream 1006 Mengzhu （数学推导）

题目链接： [ACdream 1006][] 题意： ![这里写图片描述][SouthEast] ![这里写图片描述][SouthEast 1] ![这里写图

﹏ヽ暗。殇╰゛Y/ 2022年06月13日 02:08/ 0 赞/ 232 阅读

相关 Java开发笔记（二十二）神奇的冒号

Java中的标点符号主要有两类用途，一类是运算符，包括加号+、减号-、乘号\、除号/、取余号%、等号=、大于号>、小于号<、与号&、或号|、非号!、异或号^等等，另一类则是分隔

拼搏现实的明天。/ 2022年04月18日 06:51/ 0 赞/ 321 阅读

相关数学系列（二）自然数、分数、小数、算数、代数

从无到有数的概念出生不久的孩子你觉的他认识1、2、3类似的数字吗？应该都不知道，可见数字的概念也是随着我们人类成长逐渐认识到的，英国经济学创立者亚

太过爱你忘了你带给我的痛/ 2022年03月06日 12:52/ 0 赞/ 541 阅读

相关二分

一、整数集合上的二分 1. 具体问题具体分析，左右半段哪个是可行区间，以及mid归属哪一半 2. 根据分析结果，选择一个配套形式 1. \\(r=mi

迈不过友情╰/ 2022年01月10日 04:37/ 0 赞/ 367 阅读