zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16531978.html 概念 下面除法皆表示整除 求： ∑i=1nni\sum_{i=1}^n \frac n i i=1∑n​in​ 显然，暴力 O(n)O(n)O(n)，但有很多结果是相同的，所以可以分段每一段分别处理，大概有 n\sqrt nn​ 段 令这一段的左端点（最小值）为 lll，设 k=nlk=\dfrac n lk=ln​，我们要找一个最大值 rrr 满足 nr=k\dfrac n r=krn​=k，显然 r=nnlr=\df...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16531914.html 题目链接 题目 给定两个整数 l 和 r ，对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ，把 x 的所有约数全部写下来。对于每个写下来的数，只保留最高位的那个数码。求1～9每个数码出现的次数。 思路 显然数论分块 然后统计一下每一块内1到9出现的情况乘上 n/ln/ln/l 即可 Code 12345678910111213141516171819202122232425262728293031323...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16531877.html 题目地址 题目 求 ∑i=1n∑j=1m(n mod i)×(m mod j),i≠j\sum_{i=1}^{n} \sum_{j=1}^{m} (n \bmod i) \times (m \bmod j), i \neq j i=1∑n​j=1∑m​(nmodi)×(mmodj),i=j mod 19940417 的值 思路 设 n≤mn\leq mn≤m ∑i=1n(n mod i)×∑j=1m(m mod j)...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16531857.html 相关文章： 拓展欧几里得小结 内容基本一样 一本通提高篇之同余问题（课堂笔记）有些例题 其他 博客相关文章 这篇文章内容之前已经记过一次了，但用的时候又忘了，再记一下 之前的这篇会详细很多 拓展欧几里得复习 ax+by=gcd⁡(a,b)\Large ax+by=\gcd(a,b) ax+by=gcd(a,b) 其中 a,ba,ba,b 已知，求 x,yx,yx,y 正常的推导应该都会，拆开后合并同类项最终化为： a...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16529785.html 题目地址 题目 若 xxx 分解质因数结果为 x=p1k1p2k2⋯pnknx=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}x=p1k1​​p2k2​​⋯pnkn​​，令f(x)=(k1+1)(k2+1)⋯(kn+1)f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)f(x)=(k1​+1)(k2​+1)⋯(kn​+1)，求 ∑i=lrf(i)\sum_{i=l}^rf(i)∑i=...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16529718.html 题目地址 题目 思路 以下分数皆表示整除 max⁡(n mod i)=max⁡(n−ni×i)=n+max⁡(−ni×i)=n−min⁡(ni×i)\Large\max(n\bmod i)\\\Large=\max(n-\frac n i\times i)\\\Large=n+\max(-\frac n i\times i)\\\Large=n-\min(\frac n i \times i) max(nmodi)=m...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16529601.html 题目地址 题目 给出正整数 nnn 和 kkk，请计算 G(n,k)=∑i=1nk mod iG(n, k) = \sum_{i = 1}^n k \bmod i G(n,k)=i=1∑n​kmodi 其中 k mod ik\bmod ikmodi 表示 kkk 除以 iii 的余数。 思路 数论分块 下面除法默认下取整 G(n,k)=∑i=1nk mod i=∑i=1n(k−ki×i)=n×k−∑i=1ni×ki\L...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16519140.html 题目链接 题目 思路 方法一 暴力循环 [l,r][l,r][l,r]，判断是否满足题意的数量，复杂度 O(n2q)O(n^2q)O(n2q) 方法二 对于上面的方法，显然，其实我们可以只枚举有多少个满足 Sj=T2S_j=T_2Sj​=T2​，那么有多少个 iii 满足 Si=T1S_i=T_1Si​=T1​ 是可以用前缀和预处理后 O(1)O(1)O(1) 算出来的。复杂度 O(nq)O(nq)O(nq) 方法三 ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16518844.html 比赛地址 比赛情况 排名：2 mark：100+100+100+100=400 题目分析 A 按题意输入输出 B 去掉空格和新号后判回文 C 首先进行第一次变换可以发现最大值为 9^2\time 18=1458，所以预处理一下就行 D 先计算和，如果是3的倍数就不用。 否则，如果模3余1则要么一个模三余一，要么两个模三余二。 模3余2同理 PJ、TG组有时间再补

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16513099.html 比赛地址 比赛情况 排名：885 AC：5 / 8 题目分析 A 签到题 B W记为1，L记为3，D记为2，判断 (i,j)(i,j)(i,j) 与 (j,i)(j,i)(j,i) 的和是否为4 C map+string即可 D 设 dpi,jdp_{i,j}dpi,j​ 代表前 iii 次末尾有连续 jjj 次1的最大价值，记 ziz_izi​ 代表连续 iii 次的奖励（没有则为0） dpi,0=max⁡1≤j≤i−...