首页 > 其他分享 >数论模拟(1) 小朋友们,我们今天来找规律

数论模拟(1) 小朋友们,我们今天来找规律

时间:2024-05-02 11:23:03浏览次数:31  
标签:10 leq 数论 偶数 cdot 小朋友 模拟

\(60\) 分钟,干出来 \(30\) 至 \(40\) 分(满分 \(50\)),最后一步没写出来还是有点 rz.

题目:
求最小的整数 \(n\),使得对至少两个不同的奇素数 \(p\),有

\[\sum_{k=1}^{n}(-1)^{v_p(k!)}<0. \]

解:

根据 \(v_p\) 函数的性质,可以对所有正整数进行规律性地分块,每块中的 \(v_p\) 值都是相同的:除了第一个块有 \(p-1\) 个数,其他块都有 \(p\) 个数.

对 \(p\) 的倍数 \(m\),如果 \(v_p(m)\) 是偶数,则该数所在的块对总和产生的贡献和前一块相同;若是奇数,则和前一块相反.

我们先来看 \(n<p^2\) 的情况:显然每一块的贡献分别是 \(p-1, -p, p, -p, p, \cdots, -p, p\),故当 \(n=mp-1\),\(m\) 为偶数时总和是负数.

接着讨论 \(p^2 \leq n < p^3\) 的情况,发现这样的 \(n\) 不存在.

讨论 \(p^3 \leq n < 2 \cdot p^3\) 的情况,发现 \(n\) 符合条件当且仅当 \(n=2p^2-mp-1\),\(m\) 为 不大于 \(p\) 的偶数.

我们猜想这道题的答案不是很大. 如果你算到了之后的情况,那你就是纯纯的 无效思考 浪费时间.

之后就可以枚举各个小素数,容易发现 \(n=229=2\cdot 5^3-4\cdot 5 - 1= 10\cdot 23 - 1\) 最小.

出处: 2022 年 2 月 HMMT 代数与数论第 10 题.

评价: 还行,但是我脑子有毛病,最后一步去解不定方程.

妈妈,我要学数论!

标签:10,leq,数论,偶数,cdot,小朋友,模拟
From: https://www.cnblogs.com/bpbjs/p/18169111

相关文章

  • 模拟集成电路设计系列博客——6.2.5 毛刺
    6.2.5毛刺数字逻辑的毛刺是转换器进行高速工作时的一个主要问题,\({b_1,b_2,...,b_N}\)与开关信号直接关联。毛刺的来源是开关切换不同信号的延迟。例如,但数字码从\(0111...1\)切换到\(1000...0\)时,所有的\(N-1\)的LSB都关闭,而MSB打开,然而,有可能LSB开关的电流先于MSB开关的电流关......
  • 模拟集成电路设计系列博客——6.2.2 基于R-2R的转换器
    6.2.2基于R-2R的转换器为了避免二进制权重转换器中的巨大电阻比例,可以通过引入串联电阻来使得阵列中的信号缩放,如下图所示:注意此处的节点电压\(V_A\)等于参考电压\(V_{ref}\)的四分之一,作为\(3R\)的串联电阻引入的结果。同时注意一个额外的\(4R\)被添加在地处,从而使得从\(3R\)......
  • 模拟集成电路设计系列博客——6.2.3 电荷重分布开关电容转换器
    6.2.3电荷重分布开关电容转换器电荷重分布开关电容转换器的基本思想是将开关电容增益放大器的输入电容替换为一个可编程电容阵列(PCA,ProgrammableCapacitorArray),如下图所示:如我们之前在开关电容增益放大器时讨论的一样,上图中的电路对于放大器输入失调电压,\(1/f\)噪声和有限放......
  • 模拟集成电路设计系列博客——6.2.1 二进制权重电阻转换器
    6.2.1二进制权重电阻转换器一种主流的实现D/A转换器的方式是将一组信号以二进制方式进行组合。这组二进制信号可以是电流(在电阻或者电流方式中),但二进制权重的电荷也经常使用。在这个章节中,将首先介绍店主方式,然后是和电荷重分布的模式和电流模式。在这个远离下并不能保证单调性,......
  • 5.1模拟赛 T3 记录
    题面首先显然我们可以把序列变成几段连续段,如果连续段中有一个数不一样,显然不满足了。现在就要求使得这几个连续段都独立不能连成一个大段地方案数,考虑容斥。考虑进行连续段\(dp\),套路的,我们只要确认一个段最小的数是什么就可以知道整个段的值域,所以我们只需要确定连续段之间......
  • 模拟微任务 判断是否有对应的api
    if(typeofPromise!=='undefined'&&isNative(Promise)){}functionrunMicrotask(func){if(typeofPromise==='function'){Promise.resolve().then(func)return}if(typeofMutationObserver==='functi......
  • 2024/5/1 NOIP 模拟赛
    \(T1\)觉得很弱小的字符串,\(Trick\)也比较明显。\(\texttt{T2}\)神仙题。输入\(n\)个数\(\{a\}\),问在\(\{a\}\)中,每个\(a_i\)至多可以减去\(k\)(不能减成\(0\)),至多删去\(f\)个数,求最后合法的公约数\(g\)的全部方案。60考虑如果\(g\)是\(a_i\)的约数,那......
  • 初三奥赛模拟测试5
    初三奥赛模拟测试5点击查看快读快写代码#include<cstdio>usingnamespacestd;//orzlaofudasuan//modifiednamespaceio{ constintSIZE=(1<<21)+1; charibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];intf,qr; //......
  • CF EDU164-E-数论分块
    link:https://codeforces.com/contest/1954/problem/E有一排怪物,第\(i\)只有\(a_i\)的血,每次攻击可以选择在\(i\)处放一个技能,技能会一直向左/右以相同的\(k\)点伤害扩散,直至遇到边界或已经死亡的怪物。问最少需要放几次技能?需要对所有\(k\)回答答案。\(n,a_i\leq10^......
  • YC278A [ 20240420 CQYC省选模拟赛 T1 ] 作画(paint)
    题意给定排列\(S\),最初\(S_i=i\)。每次进行以下操作,进行\(t\)次。选择下标\(i,j\),使得\(S_i=S_j\)。求进行\(t\)次后,\(S\)有至少\(k\)种数字的概率。\(n\le10,t\le10^{18}\)。Sol考虑概率转方案,变为有多少种方案使得最终状态有\(k\)种数字。不......