首页
A
qgoudnwi
当前主题：自动模式
查看保存队列
搜索
专栏文章
CF2134B
B
BrotherCall
Illenials
2025/08/29 05:37
个人记录
参与者 1
已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
当前评论
0 条
当前快照
1 份
快照标识符
@mio2vq1t
此快照首次捕获于
2025/12/02 12:28
3 个月前
此快照最后确认于
2025/12/02 12:28
3 个月前
查看原文
时光机
更新文章
复制链接
复制快照链接
复制正文 Markdown
思路
1
1
1
：
题意转化为：
找到一个序列
{
x
i
}
\{x_i\}
{
x
i
}
满足
0
≤
x
i
≤
k
0\le x_i \le k
0
≤
x
i
≤
k
。
∃
m
>
1
,
∀
i
∈
n
,
a
i
+
x
i
k
≡
0
(
m
o
d
m
)
\exist m > 1,\forall i \in n,a_i + x_ik \equiv 0 \pmod m
∃
m
>
1
,
∀
i
∈
n
,
a
i
+
x
i
k
≡
0
(
mod
m
)
找到第一个
gcd
(
k
,
m
)
=
1
\gcd(k , m) = 1
g
cd
(
k
,
m
)
=
1
的
m
m
m
即可。
这个
m
m
m
数量级是
log
\log
lo
g
的。
思路
2
2
2
：
还是得发现
gcd
(
k
,
m
)
=
1
\gcd(k , m) = 1
g
cd
(
k
,
m
)
=
1
，由于
0
≤
x
i
≤
k
0 \le x_i \le k
0
≤
x
i
≤
k
，且
gcd
(
k
,
k
+
1
)
=
1
\gcd(k , k + 1) = 1
g
cd
(
k
,
k
+
1
)
=
1
。
所以
m
m
m
直接取
k
+
1
k + 1
k
+
1
，发现
(
a
i
+
k
a
i
)
m
o
d
(
k
+
1
)
=
0
(a_i + ka_i) \bmod (k+1) = 0
(
a
i
+
k
a
i
)
mod
(
k
+
1
)
=
0
，所以
x
i
=
a
i
m
o
d
(
k
+
1
)
x_i = a_i \bmod (k + 1)
x
i
=
a
i
mod
(
k
+
1
)
。
相关推荐
评论
共 0 条评论，欢迎与作者交流。
最新优先
最早优先
搜索
正在加载评论...