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

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

智能推荐

android的binder机制研究（C++部分）分享-程序员宅基地

文章浏览阅读300次。转自：http://ytydyd.blog.sohu.com/139026338.html （一）概述 android的binder机制提供一种进程间通信的方法，使一个进程可以以类似远程过程调用的形式调用另一个进程所提供的功能。binder机制在Java环境和C/C++环境都有提供。 android的代码中，与C/C++的binder包括一些类型和接口的定义和实现，相关的代码在下面这几个文件中： framew

DLL中调用约定和名称修饰（二）_dll __thiscall-程序员宅基地

文章浏览阅读573次。4、thiscallthiscall调用约定是C++中的非静态类成员函数的默认调用约定。thiscall只能被编译器使用，没有相应的关键字，因此不能被程序员指定。采用thiscall约定时，函数参数按照从右到左的顺序入栈，被调用的函数在返回前清理传送参数的栈，只是另外通过ECX寄存器传送一个额外的参数：this指针。这次的例子中将定义一个类，并在类中定义一个成员函数，代码如下： _dll __thiscall

关键字final的含义及用法_final关键字-程序员宅基地

文章浏览阅读1.2w次，点赞8次，收藏24次。1.关键字final表示最终的，不可变的。2.关键字final可以修饰变量、方法，还有类3.final修饰的类无法被继承4.final修饰的方法无法被覆盖，无法被重写5.final控制不了能不能调用的问题，表示的是最后的，不能变的，不能改的。6.final修饰的变量只能赋一次值7.final修饰的引用：该引用只能指向1个对象，并且它只能永远指向该对象，并且无法指向其他对象。并且在该方法执行过程中，该引用指向对象之后，该对象不会被垃圾回收期回收直到当前方法结束，才会释放空间_final关键字

Php5.6.15-fpm的运行机制源码剖析-程序员宅基地

文章浏览阅读189次。源码版本：Php5.6.15源码目录：sapi/fpm/fpm说明：源码的主要功能在上面直接注解=============>>start<<================================主进程信号初始化，依据收到的信号类型，进行处理int fpm_signals_init_main() /* {{{ */{struct sigactio...

Flash 平台技术的优化(二) 节省内存_单片机优化程序减少flash占用-程序员宅基地

文章浏览阅读975次。节省内存对于应用程序（尤其桌面应用程序）开发一直非常重要。然而，内存的使用量对移动设备来说非常重要，因此有必要限制应用程序占用的内存量。显示对象选择适当的显示对象。ActionScript 3.0 包含很多显示对象。要限制内存用量，最简单的优化技巧之一是使用合适类型的显示对象。对于非交互式简单形状，请使用 Shape 对象。对于不需要时间轴的交互式对象，请使用 Sprite 对象。对于使用时间轴的动画，请使用MovieClip 对象。应始终为应用程序选择最有效的对象类型。以下_单片机优化程序减少flash占用

Bayer彩色滤波器-程序员宅基地

文章浏览阅读6.7k次。Bayer滤波器是一个将RGB三种彩色安排在单片CCD像元阵列上的彩色滤波器排列方式，如下图所示。Bayer滤波器又常被称作彩色滤波马赛克。每一个像元都用一微小的红、绿、蓝滤色片覆盖，其中绿色像元的数量是红和蓝像元的数量的二倍。这是因为人眼对绿色图像细节的分辨能力比红和蓝的高。从图上图中的（b）部分可以看出，每四个像元组成的方块内，都含有二个绿色像元，而红和蓝色像元