【Nowcoder】数论知识点


补充学习的知识点

数论前置知识部分学习笔记

题目

牛牛与LCM

【题意】

求给出的 \(n\) 个数能够选择其中的几个使得 LCM 为 \(x\) 。

【分析】

能够组成 LCM 的数 \(a_i\) 必然满足 \(x\; mod\; a_i =0\) 。

而显然,尽量多这样的 \(a_i\) 所求出来的 LCM 一定更接近于或者等于 \(x\) 。

于是我们对所有满足的 \(a_i\) 求 LCM ,判断是否等于 \(x\) 即可。

 

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 67,589

Categories

Archive

Comments