题目描述
大家都认为 Sheauhaw 有一个庞大的后宫, 于是后宫管理系统应运而生. 该后宫管理系统为了满足 Sheauhaw 的特殊需求, 众生平等, 甚至可以录入任何实体的信息! 下面是该系统的运营方式:
后宫管理系统中一共存储了(n)个实体的信息, 每个实体都有一个从(1)到(n)的编号. 你可以向后宫管理员 Zeondik 查询某个实体的编号, 管理系统会返回一个编号(x).
但是, 由于系统不稳定, 你暂时不能确定这个(x)的正确性, 假设真实编号是(k). 好在你可以向 Sheauhaw 核实该返回值, 但是 Sheauhaw 比较神秘, 不会直接告诉你对或者错, 也不会直接告诉你编号, 而是用一种奇怪的方式核实: Sheauhaw 可以让你呈上一个整数(y), 然后大发慈悲地告诉你(gcd(k,y)).
聪明无比的你一定有一个合适的(y)的选择, 将这个数字告诉 Sheauhaw 可以准确地判断(x)的正确性. 然而, Sheauhaw 喜欢小的东西, 管理员 Zeondik 要求你在所有合适的(y)中挑选一个最小的(y)告诉 Sheauhaw, 并检查你的(y)是否最小. 但(y)可能很大, 你只需要输出(y)对(920,011,128)取模的数值即可: 如果你的输出(y'equiv y_m () (mod) (920,011,128)), Zeondik 就会让你通过.
如果没有合适的(y), 输出(-1).
输入格式
第一行一个整数(T), 表示查询次数.
每组数据输入一行, 每行两个整数(n,x), 表示编号范围和系统输出.
输出格式
每组输出输出一行, 一行一个整数, 表示(y)对(920,011,128)取模后的值. 如果没有合适的选择, 输出(-1).
数据范围
(1leq T<10)
(1leq kleq nleq 10^7)
思路
枚举y显然不太好，我们换个思路，枚举gcd的值g，并判断哪些g对我们更有用。
显然g必须整除x，那么如果g是x的真因子，那么g本身这个数就满足(gcd(g,x)=g),并不是独一无二的。
所以我们断定，合理的y必然满足(gcd(x,y)=x)，也就是说y是x的倍数。
那么可能扰乱我们的只剩1~n中x的倍数了。
那么对于任意k(k>1) 我们要保证(gcd(y,kx) eq x)，相当于(gcd(frac{y}{x},k) eq 1)，而k的范围是((1,frac{n}{x}])，所以 (frac{y}{x}) 就是([1,frac{n}{x}])之间所有素数的乘积。
总结一下，令(f(x))表示([1,n])内所有素数乘积，则(ans(n,x)=x*f(frac{n}{x}))。
代码
#include <cstdlib>
#define mod 920011128
#include <algorithm>
#define maxn (int)(1e7 + 1)
#define ll long long
using namespace std;
ll f[maxn], p[maxn];
int book[maxn], cnt = 0, t[11][2];
int main() {
int T, i, j, n = 0;
ll ans;
scanf("%d", &T);
for (i = 1; i <= T; i++) {
scanf("%d%d", &t[i][0], &t[i][1]);
n = max(n, t[i][0]);
}
book[1] = 1;
f[0] = f[1] = 1;
for (i = 2; i <= n; i++) {
if (!book[i]) {
p[++cnt] = i;
}
for (j = 1; j <= cnt && i * p[j] <= n; j++) {
book[i * p[j]] = 1;
if (!(i % p[j]))
break;
}
}
for (i = 2; i <= n; i++) {
if (book[i])
f[i] = f[i - 1];
else
f[i] = f[i - 1] * i % mod;
}
for (i = 1; i <= T; i++) {
ans = t[i][1] * f[t[i][0] / t[i][1]] % mod;
printf("%lld
", ans);
}
return 0;
}