首页 > 其他分享 >7.29 day6数学

7.29 day6数学

时间:2023-07-29 10:11:48浏览次数:41  
标签:7.29 day6 复杂度 frac 555 数学 quad c2 质因数

如果没问题就是300

T1

线性筛里,每个数都会被他最小的质因数筛到,令

\(f(x)=[x\%p==0] \quad p \in dangerous\)

这显然是个完全积性函数,线性筛即可

时间复杂度:\(O(n)\)

T2

考虑这棵树实质上是一个以1为根,边权为大于父亲边权的质数,节点值则为到根路径上边权累乘

那么我们要求x,y之间路径实质上是\(dep[x]+dep[y]-dep[lca]*2+1\)

lca则是x,y相同最多的最小质因数

比如 111 555
111 = 3 * 37
555 = 3 * 5 * 37

LCA(111,555)=3

每个数最小质因数显然也可以线性筛直接求

时间复杂度:\(O(n\log n)\)

T3

考虑直接枚举\(\frac{y+x}{y-x}\)的值

设\(c1=y+x\quad c2=y-x\)

\[y=\frac{c1+c2}{2}\quad x=\frac{c1-c2}{2} \]

值最大到2n-1

可以证明,我们每次枚举到的都是可能的x,y,这样的最多4n组,时间复杂度\(O(4n)\)

标签:7.29,day6,复杂度,frac,555,数学,quad,c2,质因数
From: https://www.cnblogs.com/Linnyx/p/17589341.html

相关文章

  • DAY6
    指针练习声明变量:pstr是一个指向数组的指针,该数组内含20个char类型的值char(*pstr)[20];编写一个函数,返回储存在int类型中数组中的最大值,并在一个简单的程序中测试该函数#include<stdio.h>intget_max(intnumber[],intn){intmax=number[0];inti;......
  • VuePress@next 使用数学公式插件
    VuePress@next使用数学公式插件搞了一个VuePress1.0的现在升级了一下,但是使用数学公式的插件老报错啊!经过不懈努力,终于搞定了。现在记录一下。VuePress介绍VuePress是一个以Markdown为中心的静态网站生成器。你可以使用Markdown来书写内容(如文档、博客等),然后VuePress......
  • Latex常用数学符号输入方法
    引用CSDN博文https://blog.csdn.net/qq_25368751/article/details/87888974......
  • 数学证明助手 Lean
     官方: Lean(leanprover.github.io)社区:Leancommunity(leanprover-community.github.io)(github.com):  leanprover-community/mathlib4:Workinprogressmathlibportforlean4  ......
  • 【转载】LaTeX 数学公式大全
    转载自IowaBattleship大佬的LaTeX公式大全。LaTeX入门貌似有些东西在博客园渲染不出来数学公式的插入将数学公式写在$$之间,代表的是插入行内数学公式(通常称为行内模式)。将数学公式写在$$$$之间,会使公式独立成一行并强制居中(通常称为独立模式)。声调/变音符号......
  • 年度书单盘点|大数据告诉我,啃下这10本,数学一定差不了
    学好数理化,走遍天下都不怕,数学是门难啃的硬骨头,基础学科的教育越来越受到重视,而今年数学书的受欢迎程度,更是在图灵众多图书品类中一骑绝尘!有人嘴上说着“数学我恨”,但总体来看大家对学习和了解数学的热情越加浓烈。想必各位读者也和小编一样好奇,究竟就是什么样的数学书才能让一众网......
  • Codeforces Round #885 数学专场
    妙,我只能说妙。今天补DEF发现除了F诡秘的杨辉三角,我都能独立做出来。但为什么我感觉DE难度不如C!!!!A题意:一个人站在\((x,y)\)处,而其他人分别在\((x_1,y_1)\dots(x_n,y_n)\),每一次这个人先移动一步到上下左右四个格子,然后其他\(n\)个人再移动一步,求是否永远这个人与其他人不......
  • 《信息安全数学基础》第三章:循环群
    循环群(medium)循环群定义群\(G\)中的元素都是某个元素\(g\)的幂,则\(G\)称为循环群。\(g\)是\(G\)的一个生成元,\(g\)生成的循环群\(G\)记为\((g)\)或\(<g>\)。循环群分类无限循环群:\(\{...,g^{-2},g^{-1},g^{0},g^{1},g^{2},...\}\),其中\(g^{0}=e\)......
  • 【学习笔记】【数学】概率与期望
    前言如果不小心发表出去了那么大概率是我手滑点错了,没有更新完那就是我也在学,有问题请@我。另外有同学告诉我概率期望其实是动态规划?基础知识:互斥事件:事件\(A\)和\(B\)的交集为空,\(A\)与\(B\)就是互斥事件,也叫互不相容事件。也可叙述为:不可能同时发生的事件。如\(A......
  • 晚新闻数学讲评
    这部份内容很多思路都在学校讲过,有的干脆原题搬上来了,希望大家借此对小学期学习的内容进行回顾。这道题我们发现,如果能都构成\(a_{2n+1}+a_{2n}=6n-1\)的形式就好了。但是有一个\(a_1\),怎么办呢?我们不妨令\(n\)为偶数,那么\(a_{n+1}+a_n=3n-1\)且\(a_{n}-a_{n-......