Modulo Query ZOJ - 3940 （区间取模）_七九河开的博客-程序员秘密

技术标签：数论

题目

https://cn.vjudge.net/problem/ZOJ-3940

题意

给你n个模数，和一个0-m范围，Q次询问，每次问范围内有多少数结果是给定的数

思路

区间取模，对x个区间取模，最多会产生x+1个区间，即x个0-（x-1）的区间合并为一个，和0-（<x）的区间

所有最后最多会有2*n个区间，

对于所有的查询x，查找有多少区间又端点大于等于x，即答案

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+7;
struct node
{
    int r,cnt;
    bool operator < (const node &a) const
    {
        return r < a.r;
    }
}a[500005];
int sum[500005];
int qw[500005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        node u;
        u.r = m,u.cnt = 1;
        priority_queue<node> q;
        q.push(u);
        for(int i = 1;i <= n;i++)
        {
            int x;
            scanf("%d",&x);
            while(q.top().r >= x)
            {
                u = q.top();
                q.pop();
                int cnt = u.cnt;
                while(!q.empty()&&q.top().r == u.r)
                {
                    cnt+=q.top().cnt;
                    q.pop();
                }
                node v;
                v.r = x - 1;
                int num = cnt*(u.r/x);
                v.cnt = num;
                q.push(v);
                v.r = u.r % x;
                v.cnt = cnt;
                q.push(v);
            }
        }
        int p = 0;
        while(!q.empty())
        {
            a[p].r = q.top().r;
            a[p++].cnt = q.top().cnt;
            q.pop();
        }
        sort(a,a+p);
        memset(sum,0,sizeof(sum));
        for(int i =p-1;i >= 0;i--)
        {
            sum[i] = sum[i+1] + a[i].cnt;
            qw[i] = a[i].r;
        }
        int Q;
        scanf("%d",&Q);
        ll ans = 0;
        for(int k = 1;k <= Q;k++)
        {
            int x;
            scanf("%d",&x);
            int id = lower_bound(qw,qw+p,x) - qw;
            ans += (ll)k*sum[id];
            ans %= mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

本文链接：https://blog.csdn.net/sdut_jk17_zhangming/article/details/89192309

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

GCC字符集设置_code&debug的博客-程序员秘密

原文：http://www.cnblogs.com/findumars/p/5624858.htmlGCC提供了以下的参数开关来支持其它文字编码的源文件: a)-finput-charset=charset gcc在默认情况下,总是假设源代码的编码是UTF-8,如果是其它编码的源代码文件,源代码里面又用到了wchar_t的类型,则可...

《C语言及程序设计》实践参考——长方形的周长和面积_c语言长方形周长和面积编程_迂者-贺利坚的博客-程序员秘密

返回：贺老师课程教学链接 C语言及程序设计初步项目要求题目：编程序，输入长方形的两边长a和b，输出长方形的周长和面积提示：边长可以是整数也可以是小数；实现乘法的运算符是*参考解答：

作者:不详文章来源:http://www.javathinker.org/bbs/topic.jsp?db=1_dingdangxiaoma的博客-程序员秘密

作者:不详文章来源:http://www.javathinker.org/bbs/topic.jsp?db=15&topic=3348 上传日期:2007-03-03 1．更新服务器对于将MySQL安装为服务的，先使用net stop MySQL，如果没有将MySQL安装为服务，先停止服务，而后安装新的服务器软件。2．连接服务器shell> my...

1/t的傅里叶变换证明_SilentLittleCat的博客-程序员秘密

-i*pi*sgn(ω);看到很多人只给了结论，这里简单说一下证明思路：其中有一些符号变换注意一下就可以了

编写程序，用一个 for 循环计算1+3+5+7 + ……+99的值，并输出计算结果。_php1+3+5+7+9+…+99_小刚博客的博客-程序员秘密

<div style="language:zh-CN;line-height:150%;margin-top:12.0pt;margin-bottom:0pt;margin-left:0in;text-indent:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-l

动态规划 - The Levenshtein Distance 编辑距离_天涯古巷的博客-程序员秘密

（一）问题样例给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：• 插入一个字符• 删除一个字符• 替换一个字符【示例】输入：word1 = "benyam", word2 = "ephrem"输出：5（二）求解步骤1、确定状态- 找出最后一步- 化成子问题- 画出动态规划表 - 表的最后一格表示原问题， - 表的任意一格表示一个子问题- 填写动态规划表