题目来源: XJTUOJ-1168 zxh的后宫管理系统

题目链接: https://oj.skyair.org/problem/1168

题面

一共 \(T\) 组数据.

现有一个未知的整数 \(k\), 满足 \(1\le k\le n\).

现在你被宣称 \(k\) 的值等于 \(x\), 但是你不知道真假. 你现在可以提交一个任意大的正整数 \(y\), 之后获得返回值 \(\gcd(k,y)\).

你需要寻找一个合适的 \(y\), 使得你可以通过返回值来查验 \(x\)\(k\) 是否相等. 如果有很多满足条件的值, 选阿泽最小的那个. 如果没有合适的 \(y\), 输出 \(-1\).

由于 \(y\) 很大, 输出对 \(920011128\) 取模后的结果.

简要描述

给定 \(n, x\), 试给出一个最小的 \(y\), 使得 \(\forall 1\le a\le n\), 若 \(a\ne x\), 则 \(\gcd(a,y)\ne \gcd(x,y)\). 由于 \(y\) 很大, 输出对 \(920011128\) 取模后的结果.

数据范围

\[ 1\le T<10 \]

\[ 1\le k\le n\le10^7 \]

题解

答案为 \[ y=x\prod_{p\le n/x}p \] 证明见 2020 CCPC Wannafly 冬令营 Day1H 题解.

采用线性筛预处理 \([1,10^7]\) 中的所有素数. 若每次询问暴力计算素数乘积, 则复杂度为 \(O(Tn)\). 若采用前缀积, 则复杂度为 \(O(T+n)\).

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 5;
const int p = 920011128;
vector<int> ps; // 所有素数
bool chk[maxn]; // 合数为true
ll psum[maxn];
void fillPrime(int rge)
{
for (int i = 2; i <= rge; i++)
{
if (!chk[i])
ps.push_back(i);
for (int j = 0; j < ps.size() && ps[j] <= rge / i; j++)
{
chk[i * ps[j]] = true;
if (i % ps[j] == 0)
break;
}
}
}
int main()
{
const int rge = 1e7 + 3;
fillPrime(rge);
psum[0] = psum[1] = 1;
for (int i = 2; i <= rge; ++i)
if (chk[i])
psum[i] = psum[i - 1];
else
psum[i] = psum[i - 1] * i % p;
int t;
cin >> t;
for (int tt = 0; tt < t; ++tt)
{
ll n, k;
cin >> n >> k;
cout << k * psum[n / k] % p << endl;
}
return 0;
}