[题解] 头脑风暴专题

写在前面

这篇博客记录一下这些天来做（和看到）的思维题，昨天是越做越有趣，越做越起劲（其实是奶茶喝多了睡不着），直接导致了我又一不小心想出了一些（可能）很鬼酷的思维题。

持续更新中……

CodeForces 892D Gluttony

传送门

题目大意

给你$n$个不同数字组成的数组$a$，现在再任取$k$个数$\{x_1, x_2,\dots, x_k\} (1 \leq x_i \leq n, 0 < k < n)$。

要你求出$a$数组的某种排列$b$，满足：$\displaystyle\sum_{i = 1}^{k}{a_{x_i}} \neq \displaystyle\sum_{i = 1}^{k}{b_{x_i}}$

其中$1 \leq n \leq 22,1 \leq a_i \leq 10^9$。

题解思路

初看题目，觉得$n$很小，或许是暴力？但是$(22!)^2$有点大…时间上肯定过不去了。

于是转换思路，由于答案并不唯一，所以我是不是有办法构造出这样一个$b$数组，使得$\displaystyle\sum_{i = 1}^{k}{b_{x_i}}$尽可能地大于（或小于）$\displaystyle\sum_{i = 1}^{k}{a_{x_i}}$？

这么一想，这个$b$似乎很好构造？假设$a_i$是$a$中的第$k$小，那么只要让对应的$b_i$是$a$的第$k+1$小不就好了（当然$a$中的最大值要让$b$中对应的数是$a$中的最小值）？

这样能保证不取到$a$中最大值的情况下，任取$k$个数$\{x_1, x_2,\dots, x_k\} (1 \leq x_i \leq n, 0 < k < n)$，均满足$\displaystyle\sum_{i = 1}^{k}{a_{x_i}} < \displaystyle\sum_{i = 1}^{k}{b_{x_i}}$。

如果取到$a$的最大值能保证满足题目要求吗？答案是肯定的：

假设上述未取到的$n-k$个数分别为$\{x_{k+1}, x_{k+2},\dots, x_n\}$，由于$\displaystyle\sum_{i = 1}^{n}{a_{i}} = \displaystyle\sum_{i = 1}^{n}{b_{i}}$，所以必然有$\displaystyle\sum_{i = k+1}^{n}{a_{x_i}} > \displaystyle\sum_{i = k+1}^{n}{b_{x_i}}$。

至此，我们也就得出一个我们想要的$b$了，同时证明了答案必然存在。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 30;
set<int> st;
int a[MAX_N], b[MAX_N];
int main() {
    int n;
    while(~ scanf("%d", &n)) {
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]), st.insert(a[i]);
        auto ed = st.end();
        --ed;
        for(int i = 1; i <= n; ++i) {
            auto it = st.lower_bound(a[i]);
            if(it != ed)
                b[i] = *(++it);
            else b[i] = *st.begin();
        }
        for(int i = 1; i < n; ++i) printf("%d ", b[i]);
        printf("%d\n", b[n]);
        st.clear();
    }
    return 0;
}

CodeForces 763A Timofey and a tree

传送门

题目大意

给你一棵有$n$个节点的树，每个节点都有染上某种颜色$c_i$，问你是否能找到一个根节点，使得其所拥有的子树$1$、子树$2$、……、子树$p$（即所有子树），满足各个子树的所有节点的颜色相同，即子树$1$里所有节点值都相同，子树$2$、……、子树$p$也是同理，假设这些值是$a_1, a_2, \dots, a_p$，它们可以相同，也可以不同。

其中$2 \leq n \leq 10^5,1 \leq c_i \leq 10^5$。

题解思路

这题其实蛮烧脑的，首先题意就有点难以理解，其次……画了很久的图才想出一个做法。

初看想到的是直接DFS走一遍，但是时间复杂度高达$O(n^2)$，显然不可取。

于是转换思路，开始去画图，偶然发现，在子树节点的颜色与这个根节点均不相同的前提下，满足题目条件的根节点必然满足：与该点连接的子树个数 = 与该点连接但颜色不同的点数。

那么顺着这个思路，我们只要求出所有两点颜色不同的的边数（这里假设为$m$），再求出每个的点与其相连的点中有多少个颜色不同的点（这里假设为$d_i$），最终只要找到一个点$x$满足$d_x = m$即可。

证明如下：

如果现在找到了这样一个根节点$x$，假设现在又在某一子树$k$上修改某个节点$y$的颜色，使得这个节点颜色与这棵子树的颜色以及根节点颜色都不同，这样会使得原本的$m + 1$，致使$x$无法成为我们想要的答案，而子树$k$上原本所有的点（除了与$x$相邻的那个点）的$d$值均为$0$，这个操作只不过是让$y$及其相连点的$d$值$+1$，由于$m > 0$，所以这些点也就不会成为新解。

只有一种特殊情况：当上述操作的这个$y$是与$x$相邻的点，且$m=1$（即这棵树是条链）时，修改这个$y$值会使得$y$成为新解，但根据题意可知，$y$没修改前也是可行答案（但不是上述前提的解）之一。

注意：这里如果有解，那么只会有一个解，想想为什么？

但是能找出来的这个根节点又不一定与子树节点的颜色不同……这样做可以吗？

答案是肯定的。

找出的根节点与某个子树节点相同时，他们之间相连的边既不会被统计到$m$，也不会统计到这两个点的$d$值里，所以对于答案是不影响的。

换言之，如果整棵树的颜色都相同，那么树上任意点都是我们想要的答案啦。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 10;
int p[MAX_N], d[MAX_N];
struct Edge {
    int x, y;
}edge[MAX_N];
int main() {
    int n, m, u, v;
    while(~ scanf("%d", &n)) {
        memset(d, 0, sizeof(d));
        for(int i = 1; i < n; ++i) {
            scanf("%d %d", &u, &v);
            edge[i].x = u, edge[i].y = v;
        }
        for(int i = 1; i <= n; ++i)
            scanf("%d", &p[i]);
        m = 0;
        for(int i = 1; i < n; ++i) {
            if(p[ edge[i].x ] != p[ edge[i].y ])
                ++d[ edge[i].x ], ++d[ edge[i].y ], ++m;
        }
        bool flag = false;
        for(int i = 1; i <= n; ++i)
            if(d[i] == m) {
                u = i;
                flag = true;
                break ;
            }
        if(flag) printf("YES\n%d\n", u);
        else printf("NO\n");
    }
    return 0;
}

LightOJ 1095 math

传送门

题目大意

给你一个$n$个数字的初始序列（即$1$ ~ $n$的升序排序），让你求在前$m$个数中固定任意$k$个数的位置，剩下的数字任意排列，可以生成多少种不同的序列？求答案取模 $10^9+7$ 后的结果。

其中$1 \leq n \leq 1000,0 \leq m \leq n,0 < k \leq m$。

题解思路

这个题目其实是很明显的组合数学题，放到这个博客里主要是这个思维略微巧妙。

观察到题目要求在前$m$个数中取$k$个数固定位置，那么另外$m-k$个数必然是要错排的，至于后面的$n-m$个数，他们要不要错排都不要紧，因为$n \leq 1000$，我们可以直接暴力枚举后面有$i$个s数进行错排，然后算出总和，即：

$Ans = C_m^k * \displaystyle\sum_{i=0}^k {(C_{n-m}^i * d_{n-k-i})}$

其中$C_m^n$代表在$m$个物品中取$n$个的组合数，$d_i$表示$i$个不同元素的错排数。

注意预处理组合数和错排数，以及数字范围（会爆int）。

当然由于取模数是质数，也可以采用逆元的方式算组合数，这里提供的是普通的预处理方式。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7;
const int MAX_N = 1010;
ll C[MAX_N][MAX_N], d[MAX_N];
void init() {
    d[0] = 1, d[1] = 0, d[2] = 1;
    for(int i = 3; i < MAX_N; ++i)
        d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % MOD;
    for(int i = 0; i < MAX_N; ++i)
        C[i][0] = C[i][i] = 1;
    for(int i = 1; i < MAX_N; ++i)
        for(int j = 1; j < i; ++j)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
int main() {
    int T, n, m, k, Case = 0;
    ll ans;
    init();
    scanf("%d", &T);
    while(T--) {
        ans = 0;
        scanf("%d %d %d", &n, &m, &k);
        for(int i = 0; i <= n-m; ++i)
            ans = (ans + C[n-m][i] * d[n-k-i] % MOD) % MOD;
        ans = ans * C[m][k] % MOD;
        printf("Case %d: %lld\n", ++Case, ans);
    }
    return 0;
}

NOIP2017 Day1 T1 小凯的疑惑

传送门（洛谷）

题目大意

给你两个正整数$a$和$b$，保证两个数互质。问这两个数最大不能组成的数是多少？

其中$1 \leq a, b \leq 10^9$。

题解思路

不得不说这D1T1可能是我见过最难想到的题目了……除了打表找规律我几乎没有任何太大想法，想想当初要是复读一年遇到这题可能连个60分都拿不到？

但其实是道数论题，摘录网上某dalao的解释：

不妨设$a < b$，所求答案为$x$。
若有$x \equiv ma \pmod{b} (1 \leq m \leq b-1)$，即$x = ma + nb (1 \leq m \leq b-1)$
显然当$n \geq 0$时，$x$必然可以用$a, b$表示出来，不符合题意。
因此$n$最大值为$-1$，此时$x = ma - b$，再观察上述范围，当$m = b-1$时，$x$取得最大值。

$\therefore Ans = (b-1) * a - b = a * b - a - b$

AC代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    ll a, b;
    cin >> a >> b;
    cout << a * b - a - b << endl;
    return 0;
}

BZOJ 3884 上帝与集合的正确用法

传送门

题目大意

求

$\underbrace{2^{2^{2^{\sdot^{\sdot^{\sdot^{2}}}}}}}_\infty \mod p$

其中$p \leq 10^7$

题解思路

乍一看很难，实际上只是道普通的欧拉降幂应用题。

在数学上，把形如$\underbrace{a^{a^{a^{\sdot^{\sdot^{\sdot^{a}}}}}}}_n$称为$a$的$n$次迭代乘方，或者$a$的$n$次超乘方……，具体可以查阅相关资料，一般写作${}^n\!a$，特别地，${}^0\!a = 1$。

那么我们可以设$f(p)$表示${}^\infty\!2 \mod p$，由于${}^\infty\!2$必然大于$\varphi(p)$

则根据欧拉降幂公式可得$f(p) = \begin{cases} 2^{f(\varphi(p))}, & gcd(2, p) = 1 \\ 2^{f(\varphi(p)) + \varphi(p)}, & gcd(2, p) \not = 1 \end{cases} \mod p$

这里的$\varphi(p)$指的是欧拉函数。又显而易见的，当$p = 1$时，$f(p) = 0$。

这样我们就得到了一个时间复杂度接近$O(\log_2{p})$的算法，这个时候我们可以考虑筛$10^7$内的欧拉函数或者每一次递归都求一次欧拉函数。前者时间复杂度$O(p+\log_2{p})$，后者$O(\sqrt{p}\log_2{p})$。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAX_N = 1e7 + 10;
int CNT, prime[MAX_N], phi[MAX_N];
bool vis[MAX_N];
void make_prime_phi() {
    CNT = 0;
    for(int i = 2; i < MAX_N; ++i) {
        if(!vis[i]) {
            prime[++CNT] = i;
            phi[i] = i-1;
        }
        for(int j = 1; j <= CNT && i*prime[j] < MAX_N; ++j) {
            vis[ i*prime[j] ] = true;
            if(i % prime[j] == 0) {
                phi[ i*prime[j] ] = phi[i] * prime[j];
                break ;
            } else phi[ i*prime[j] ] = phi[i] * (prime[j]-1);
        }
    }
}

ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}

ll qmod(ll a, ll n, ll MOD) {
    ll ans = 1LL;
    for(; n; n >>= 1, a = a*a % MOD)
        if(n & 1) ans = ans*a % MOD;
    return ans;
}

ll f(ll p) {
    if(p == 1) return 0LL;
    ll d = gcd(2, p), tmp = f(phi[p]);
    if(d != 1) tmp += phi[p];
    return qmod(2, tmp, p);
}

int main() {
    make_prime_phi();
    int T;
    ll p;
    scanf("%d", &T);
    while(T--) {
        scanf("%lld", &p);
        printf("%lld\n", f(p));
    }
    return 0;
}

CodeForces 977D Divide by three, multiply by two

传送门

题目大意

有个人任取一个数字$x$，随机地进行$n-1$次下面两种操作：

1. 将$x$除以$3$，前提是$x \mod 3 = 0$
2. 将$x$乘$2$

这样能得到$n$个数字，现在给你这$n$个数字的某种排列，让你还原出一种满足上述两种操作的排列。即题目要求的序列满足：若第$i(i < n)$个数为$x_i$，则$x_{i+1}$必须是$x_i / 3$或$2 \cdot x_i$

题目保证答案一定存在，其中$2 \leq n \leq 100$，$1 \leq x_i \leq 3 \cdot 10^{18}$

题解思路

根据题意易证，这$n$个数都是不相同的。

所以有一种做法是深搜，任意枚举一个数字$x$，按它的操作搜索可以排在这个数字后面的数，由于题目保证有解，所以易知满足条件的数只有一个，假设为$y$，再用$y$不断深搜下去。最后用同样的方法去搜索$x$前面的数，最后必然得到一个满足题意的序列。

时间复杂度大概在$O(n) - O(n^2)$，对于这个题目都可以过。

这里提供一个更加巧妙的做法（这样才符合头脑风暴专题嘛）

既然题目保证答案一定存在，那么我们可以假设$x_i = 3^{j_i} \cdot 2^{k_i} \cdot p$，其中$p$可能是任意非负整数。

则$x_{i+1} = 3^{j_{i+1}} \cdot 2^{k_{i+1}} \cdot p$必然满足$j_{i+1} \leq j_i$且$k_{i+1} \geq k_i$，那么我们只要按照这样的规则去对原有序列进行排序，就能找到一个满足题目要求的序列。

即假设现在有两个数$a, b$，若$a$所含的$3$因子较多，$a$的优先级就较高，否则去比较所含$2$的因子数，较少的优先级较高（实际上就是较小的数优先级较高）。

事实上，上面这个做法恰巧证明了，满足题目的解有且只有一种。

AC代码

#include <cstdio>
#include <algorithm>
using namespace std;

#define ll long long
const int MAX_N = 110;
ll a[MAX_N];

inline int get_cnt(ll x) {
	int ret = 0;
	while(x % 3 == 0)
		++ret, x /= 3;
	return ret;
}

bool cmp(ll x, ll y) {
	int cnt1 = get_cnt(x), cnt2 = get_cnt(y);
	if(cnt1 == cnt2)
		return x < y;
	return cnt1 > cnt2;
}

int main() {
	int n, i, k;
	ll now, tmp;
	scanf("%d", &n);
	for(i = 1; i <= n; ++i)
		scanf("%lld", &a[i]);
	sort(a + 1, a + 1 + n, cmp);
	for(i = 1; i < n; ++i) printf("%lld ", a[i]);
	printf("%lld\n", a[n]);
	return 0;
}

计蒜客 41229 super_log

传送门

题目大意

定义一个函数如下：

$\log_a^*(x) = \begin{cases} -1, &{x < 1} \\ 1 + \log_a^*(\log_a{x}), &{x \geq 1} \end{cases}$

给你两个正整数$a$和$b$，让你求一个最小的$x$满足$\log_a^*(x) \geq b$，答案可能很大，输出$x \mod m$的结果即可。

特别地，当$a = 1$时，这个$x$的最小解是$1$。

其中，$a, m \in [1, 10^6], b \in [0, 10^6]$。

题解思路

这是2019年ICPC亚洲区域赛南京站网络选拔赛的题目。

不难得出，函数$\log_a^*(x)$实际上是在求最大的$n$满足${}^n\!a \leq x$，那么对于题目来说，找一个最小的$x$满足$\log_a^*(x) \geq b$就是${}^b\!a$。所以题目是在求${}^b\!a \mod m$。

显而易见地，又是一个欧拉降幂题（逃

设$f(a, n, p) = {}^n\!a \mod p$，则根据欧拉降幂公式得

$f(a, n, p) = \begin{cases} a^{f(a, n-1, \varphi(p))}, & {\gcd(a, p) = 1} \\ {}^n\!a, & {\gcd(a, p) \not = 1, ({}^{n-1}\!a) < p} \\ a^{f(a, n-1, \varphi(p)) + \varphi(p)}, & {\gcd(a, p) \not = 1,({}^{n-1}\!a) \geq p} \end{cases}$

特别地，$f(a, 0, p) = f(1, n, p) = 1 \% p$，$f(a, n, 1) = 0$。

现在的问题是如何判断$p$和${}^{n-1}\!a$的大小，这个其实很简单，既然我们知道题目给的函数$\log_a^*(x)$是求最大的$n$满足${}^n\!a \leq x$，那么我们只要判断$\log_a^*(p)$和$n-1$的大小就可以了。

AC代码

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const ll MAX_N = 1000000 + 10;
ll CNT, prime[MAX_N], phi[MAX_N];
bool vis[MAX_N];

void make_prime_phi() {
    CNT = 0;
    memset(vis, false, sizeof(vis));
    for(ll i = 2; i < MAX_N; ++i) {
        if(!vis[i]) {
            prime[++CNT] = i;
            phi[i] = i-1;
        }
        for(ll j = 1; j <= CNT && i*prime[j] < MAX_N; ++j) {
            vis[ i*prime[j] ] = true;
            if(i % prime[j] == 0) {
                phi[ i*prime[j] ] = phi[i] * prime[j];
                break ;
            } else phi[ i*prime[j] ] = phi[i] * (prime[j]-1);
        }
    }
}

ll qmod(ll a, ll n, ll MOD)
{
    ll ans = 1;
    for(; n; n >>= 1, a = a*a % MOD)
        if(n & 1) ans = ans*a % MOD;
    return ans;
}

ll get_log(ll x, ll a) {
    if(x < 1) return -1;
    return 1 + get_log(log(x)/log(a), a);
}

ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}

ll f(ll a, ll n, ll p) {
    if(a == 1 || n == 0) return 1%p;
    if(p == 1) return 0;
    if(n == 1) return a % p;
    if(gcd(a, p) == 1) {
        return qmod(a, f(a, n-1, phi[p]), p);
    } else {
        ll k = get_log(phi[p], a);
        if(k <= n-1)
            return qmod(a, f(a, n-1, phi[p]) + phi[p], p);
        else return qmod(a, f(a, n-1, phi[p]), p);
    }
}

int main() {
    make_prime_phi();
    int T; ll a, b, m, ans;
    scanf("%d", &T);
    while(T--) {
        scanf("%lld %lld %lld", &a, &b, &m);
        printf("%lld\n", f(a, b, m) % m);
    }
    return 0;
}

CodeFoces 849A Odds and Ends

传送门

题目大意

给你$n$个数字组成的数组$a$，问你能否分出奇数个长度为奇数的子区间，且保证每个子区间的开头和末尾都是奇数。

其中$1 \leq n \leq 100, 0 \leq a_i \leq 100$。

题解思路

这个题目很容易让人想到搜索，但实际上没有那么麻烦。

首先我们知道，奇数个奇数相加（即奇数乘奇数）必然是个奇数。那么如果$n$为偶数，就一定无法分出奇数个奇数长度的子区间。

再者，因为$1$是奇数，所以如果这个数组$a$的开头和末尾都是奇数，必然是满足条件的。

最后，如果数组$a$的开头和末尾有一个不是奇数，那么分出来的子区间必然第一个的开头不是奇数或最后一个的末尾不是奇数，不满足条件。

所以我们只要判断$n$和数组$a$的开头末尾是否均为奇数就可以了。

AC代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, a[110];
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    if((n&1) && (a[1]&1) && (a[n]&1))
        printf("Yes\n");
    else printf("No\n");
    return 0;
}

CodeForces 872B Maximum of Maximums of Minimums

传送门

题目大意

给你$n$个数组成的数组$a$，要你分成连续的$k$段，取每段的最小值，得到的$k$个数中取最大值，我们假设这个值为$Ans$，问这个$Ans$最大能得到多少？

其中$1 \leq k \leq n \leq 10^5$，$a_i \in [-10^9, 10^9]$

题解思路

看数据范围就知道，这题显然不能用搜索（

首先考虑$k = 1$的情况，显然答案就是整个数组里的最小值。

又发现如果$k \geq 3$，那么一定可以将整个数组中的最大值作为一个独立的段，那么答案显而易见的是这个最大值。

现在要考虑的是$k = 2$的情况，可以枚举一个点$i$，将数组分为$a_1$到$a_i$和$a_{i+1}$到$a_n$两段，也就是只要取区间$[1, i]$的最小值和区间$[i+1, n]$的最小值中的较大值，最后在所有情况里取最大值。用线段树或者其他数据结构维护的话，时间复杂度大概在$O(n\log_2n)$。

这样这个题目就迎刃而解了，不过这里提供一个对于$k = 2$的情况更优的做法。

通过观察其实不难发现，$k = 2$时，答案必然是$a_1$和$a_n$两个数中的较大值。

证明如下：

先假设答案不是$a_1$或$a_n$，那么说明在区间$[2, n-1]$之间会有一个数（这里假设为$a_x$）大于这两个数，并且在分成的两段区间的某一段内是最小值。但是由于只分成两段，$a_1$或$a_n$必然会有一个和$a_x$在同一段内，那么$a_x$就不会是这段区间的最小值，与假设条件矛盾。

AC代码

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 10;
int a[MAX_N];

int main() {
    int n, k, ans;
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    if(k == 1) {
        ans = a[1];
        for(int i = 2; i <= n; ++i)
            ans = min(a[i], ans);
    } else if(k == 2) {
        ans = max(a[1], a[n]);
    } else {
        ans = a[1];
        for(int i = 2; i <= n; ++i)
            ans = max(a[i], ans);
    }
    printf("%d\n", ans);
    return 0;
}

CodeForces 876B Divisiblity of Differences

传送门

题目大意

给你$n$个数字组成数组$a$，问你能否在这些数字中找到$k$个数，使得这$k$个数两两相差的值对$m$取余数均为$0$，如果可以，输出这$k$个数。

其中，$2 \leq k \leq n \leq 10^5, 1 \leq m \leq 10^5, 0 \leq a \leq 10^9$

题解思路

通过观察可以发现若两个数相差的值取模某个数$m$是$0$，那么这两个数取模$m$得到的值必定相同，所以只要判断这$n$个数中是否存在至少$k$个数模$m$为同一个数即可，最后输出满足条件的$k$个数。

AC代码

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 10;
int a[MAX_N], cnt[MAX_N];

int main() {
    memset(cnt, 0, sizeof(cnt));
    int n, k, m, pi;
    bool flag = false;
    scanf("%d %d %d", &n, &k, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        ++cnt[a[i] % m];
    }
    for(int i = 0; i < m; ++i) {
        if(cnt[i] >= k) {
            pi = i;
            flag = true;
            break ;
        }
    }
    if(flag) {
        printf("Yes\n");
        for(int i = 1, j = 1; i <= k && j <= n; ++j) {
            if(a[j] % m == pi) {
                if(i == k) printf("%d\n", a[j]);
                else printf("%d ", a[j]);
                ++i;
            }
        }
    } else printf("No\n");
    return 0;
}

快跑啊，JV又来抓人了！

题目大意

这是我自己出给新生做的题，挂在学校OJ，暂时没开放题目页面，所以没有传送门啦。

题意很简单， 给你$1 \leq n \leq {10}^5$个数字$a_1 \dots a_n$，再给你一个数字$x$，求$\displaystyle\prod_{i=1}^{n }a_i$和$x$的最小公倍数$\mod (10^9 + 7)$，其中$1 \leq x, a_i < 2^{63}$。

题解思路

这题是我某天无聊看陈景润写的《初等数论Ⅰ》，恰巧想出来的小题目，对于老法师来说应该很简单吧。

众所周知，最小公倍数$lcm(a, b) = a \cdot b \div gcd(a, b)$，但因为有除法不能乱取模，所以要换种思路，即想办法找到$\displaystyle\prod_{i=1}^{n }a_i$和$x$的最大公约数，然后让$x$除以它，这里提供两种方法：

1. 由于$gcd(a, b) = gcd(b, a \mod b)$，那么我们便可以先求$\displaystyle\prod_{i=1}^{n }a_i \mod x$ ，这里可以利用__int128（如果编译器支持的话），或是写个高精度乘法和高精度取模求。

2. 对于$gcd(a \cdot b, x)$，易知其因子里必然含有$gcd(a, x)$，那么让$x$除以$gcd(a, x)$后再与$b$取最大公约数，再乘上$gcd(a, x)$就得到了$gcd(a \cdot b, x)$，即我们可以拆分成$gcd(a, x) \cdot gcd(b, x \div gcd(a, x))$，推广到$n$个数的话就是$gcd(\displaystyle\prod_{i=1}^{n }a_i, x) = gcd(\displaystyle\prod_{i=1}^{n-1 }a_i, x) \cdot gcd(a_n, x \div gcd(\displaystyle\prod_{i=1}^{n-1 }a_i, x))$，这样我们就得到了一个递推式，便可以在$O(n)$的时间复杂度内求出$x \div gcd(\displaystyle\prod_{i=1}^{n }a_i, x)$。

AC代码

• 方法1：

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll MOD = 1e9 + 7;
const int MAX_N = 1e6 + 10;

template <class T>
T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}

ll a[MAX_N];

int main() {
    int n;
    ll x;
    while (~scanf("%d %lld", &n, &x)) {
        for (int i = 1; i <= n; ++i) 
            scanf("%lld", &a[i]);
        __int128 tmp = a[1];
        for (int i = 2; i <= n; ++i) {
            tmp = tmp * a[i] % x;
        }
        tmp = gcd(tmp, (__int128)x);
        x /= (ll)tmp;
        tmp = a[1];
        for (int i = 2; i <= n; ++i) {
            tmp = tmp * a[i] % MOD;
        }
        tmp = tmp * x % MOD;
        printf("%lld\n", (ll)tmp);
    }
    return 0;
}

• 方法2：

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll MOD = 1e9 + 7;
const int MAX_N = 1e6 + 10;

template <class T>
T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}

ll a[MAX_N];

int main() {
    int n;
    ll x, ans, r;
    while (~scanf("%d %lld", &n, &x)) {
        ans = 1LL;
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", &a[i]);
            r = gcd(x, a[i]);
            x /= r;
            a[i] %= MOD;
            ans = (ans * a[i]) % MOD;
        }
        ans = ans * (x % MOD) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}