51Nod-1203-JZPLCM

ACM模版

描述

题解

这个题的解法好像好多好多,可以线段树解,自然也可以用树状数组解,还有大佬直接莫队推过,我这里用的树状数组搞得。

首先将数进行拆解,拆成素数积的形式,每次访问时,都需要获取该区间所有出现过的素数所出现的最高次,这些数的乘积便是答案。这里我们应该进行离线操作,将所有的访问都进行排序,维护每一个特征值下一个相同的位置,从左向右扫描一遍,解决每个点作为左端点的询问。大致就是这样,很好的一个题,很佩服那些会用莫队的大佬们~~~

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 5e4 + 5;
const int MOD = 1e9 + 7;

struct note
{
    int l, r, id;

    friend bool operator < (note x, note y)
    {
        return x.l < y.l;
    }
} ask[MAXN];

int n, m;
int x, y, tot;
int l[MAXN], r[MAXN];
int h[MAXN], ans[MAXN];
int tr[MAXN << 4];
int nxt[MAXN << 4];
int a[MAXN << 4];
int b[MAXN << 4];

int QPow(int x, int y)
{
    int z = 1;
    for (; y; y >>= 1, x = (ll)x * x % MOD)
    {
        if (y & 1)
        {
            z = (ll)z * x % MOD;
        }
    }

    return z;
}

void add(int x, int y)
{
    for (; x <= tot; x += x & -x)
    {
        tr[x] = (ll)tr[x] * y % MOD;
    }
}

int find(int x)
{
    int ret = 1;
    for (; x; x -= x & -x)
    {
        ret = (ll)ret * tr[x] % MOD;
    }

    return ret;
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int j = 1; j <= n; j++)
    {
        scanf("%d", &x);

        int t = sqrt(x);
        if (x == 1)
        {
            continue;
        }

        l[j] = tot + 1;
        for (int i = 2; i <= t; i++)
        {
            if (!(x % i))
            {
                int k = i;
                while (!(x % i))
                {
                    x /= i;
                    a[++tot] = k;
                    b[tot] = i;
                    k *= i;
                }
            }
        }
        if (x > 1)
        {
            ++tot;
            a[tot] = b[tot] = x;
        }
        r[j] = tot;
    }

    for (int i = 1; i <= tot; i++)
    {
        tr[i] = 1;
    }
    for (int i = 1; i <= tot; i++)
    {
        if (h[a[i]])
        {
            nxt[h[a[i]]] = i;
        }
        else
        {
            add(i, b[i]);
        }
        h[a[i]] = i;
    }

    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &ask[i].l, &ask[i].r);

        ask[i].l = l[ask[i].l];
        ask[i].r = r[ask[i].r];
        ask[i].id = i;
    }

    sort(ask + 1, ask + m + 1);

    for (int i = 1, j = 0; i <= tot; i++)
    {
        while (ask[j + 1].l == i)
        {
            ++j;
            ans[ask[j].id] = find(ask[j].r);
        }
        add(i, QPow(b[i], MOD - 2));
        if (nxt[i])
        {
            add(nxt[i], b[nxt[i]]);
        }
    }
    for (int i = 1; i <= m; i++)
    {
        printf("%d\n",ans[i]);
    }

    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU-5534-Partial Tree

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstdio> #include <algor...

    f_zyj
  • UVA-11600-Masud Rana

    ACM模版 描述 ? ? 题解 image.png ? 保存六位小数…… 代码 #include <cstdio> #include <cstring> #in...

    f_zyj
  • ZOJ-3329-One Person Game

    ACM模版 描述 ? ? 题解 kuangbin 大佬的题解,神乎其技: ? 代码 #include <iostream> #include <cstdio> ...

    f_zyj
  • 1751:分解因数

    1751:分解因数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述给出一个正整数a,要求分解成若干个正整数的乘积,即a = ...

    attack
  • P1828 香甜的黄油 Sweet Butter

    题目描述 农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜...

    attack
  • 算法细节系列(35):不一样的排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 一遍记住Java常用的八种排序算法

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    Java旅途
  • 图m着色问题

    1 问题描述:   给定无向图,m种不同的颜色。使每一种着色法使G中每条边的2个顶点不同颜色,若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色,...

    用户1154259
  • cuda测试二维block的使用

    #include "cuda_runtime.h" #include <stdio.h> #include <stdlib.h> #include <math....

    用户1154259
  • 深入理解字符串和字节数组转换

          前文中,论及字符串和字节数组的转换,虽然能够找到某个代码页,保证转换的可逆,但是在实际处理中,仍然还有一些细节问题需要注意.       最重要的...

    用户1075292

扫码关注云+社区

领取腾讯云代金券