旅途不止

问题描述

小 L 至今没有回来。这太正常，就像其他没有回来的探险者一样。没有人会提起小 L ，也没有人述说小 L 的故事。
多年以后，你也踏上了这片神秘的土地，眼前出现了一道谜题。

有一列长度为 $n$ 的数，初始值都是 $1$ 。
有 $m$ 次操作，每次对属于区间 $[l,r]$ 的数都乘上一个数 $c^b$ ，最后输出这 $n$ 个数的最大公约数。

谜题面前有一张地图，上面署名 "小 L"。

输入格式

第一行一个整数 $n$ , $n\le 10^5$
第二行，一个整数 $m$, $m \le 10^5$
接下来的 $m$ 行，每行四个整数表示 $l,r,c,b$
$1\le l\le r\le n,1\le c\le 100,0\le b\le 10^9$

输出格式

一行，一个数，代表最大公约数，答案对 $10^9+7$ 取模。

样例输入

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

样例输出

3

初始：$[1,1,1,1,1]$
第一次操作后，$[9,9,9,9,1]$
第二次操作后，$[9,36,36,36,1]$
第三次操作后，$[9,36,216,216,6]$

$\gcd(9,36,216,216,6)=3$，gcd表示最大公约数

地图上画的正是当年小 L 探索过的区域，但小 L 去了哪里还是不得而知。
地图的背面，写着如下内容：

$n$ 个数的最大公约数求法：

设第 $i$ 个数为 $a_i$，则 $a_i=\prod_j p_j^{b_{ij}}$，其中 $p_j$ 表示第 $j$ 个素数，$b_{ij}$ 表示第 $i$ 个数质因数分解之后 $p_j$ 的幂次。
则 $gcd(a_1,...,a_n)=\prod_j p_j^{\min{b_{ij}}}$。

举例求 $gcd(60,24,36,42)$

$60=2^2\times3^1\times5^1\times7^0$
$24=2^3\times3^1\times5^0\times7^0$
$36=2^2\times3^2\times5^0\times7^0$
$42=2^1\times3^1\times5^0\times7^1$

所以

$\begin{aligned}gcd(60,24,36,42)&=2^{\min(2,3,2,1)}\times3^{\min(1,1,2,1)}\times5^{\min(1,0,0,0)}\times3^{\min(0,0,0,0)}\\&=2^1\times3^1\times5^0\times7^0\\&=6 \end{aligned}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, l, r, c, b;
const ll mod = 1e9 + 7;  // 模数
ll cf[25][100005];       // 每一行对应一个素数在1到n上面各个位置出现次数的差分
// 另外写了一个程序计算了100以内的素数
ll prime[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

ll fastpow(ll disu, ll zhisu) {  // 快速幂，参数为底数、指数
    ll res = 1;
    while (zhisu) {
        if (zhisu % 2)  // 指数是否为奇数
            res = res * disu % mod;
        disu = disu * disu % mod;
        zhisu >>= 1;  // 除以2向下取整
    }
    return res;
}

void fen_jie_c() {  // 将c进行质因数分解，并且对l到r的区间进行操作
    for (ll i = 0, the_c = c; i < 25; ++i) {
        if (the_c == 1)  // 减少多余的循环
            break;
        while (the_c % prime[i] == 0) {  // 如果能被当前的质数分解
            the_c /= prime[i];
            cf[i][l] += b;  // 在这个质数(即底数)对应的差分区间上面加上相应的次数(指数)
            cf[i][r + 1] -= b;
        }
    }
}

void gcd() {  // 找出最大公约数
    ll res = 1;
    for (ll i = 0; i < 25; ++i) {  // 对全部可能的底数统计它们的次数(指数)
        ll sum = 0, mi = 1LL << (sizeof(ll) * 8 - 2);
        for (ll k = 1; k <= n; ++k) {
            sum += cf[i][k];    // 计算第k个位置的第i+1个底数的次数
            mi = min(mi, sum);  // 找出这个底数对应的最小次数
        }
        res = (res % mod) * (fastpow(prime[i], mi) % mod);  // 不取模会溢出
    }
    cout << res % mod;  // 还要再取一次模
}

int main() {
    cin >> n >> m;
    for (ll i = 0; i < m; ++i) {
        scanf("%lld %lld %lld %lld", &l, &r, &c, &b);
        fen_jie_c();
    }
    gcd();
    return 0;
}