试证：对任意我用新自然数观点证明费马方程n＞1，方程x^n+x^n-1+……+x=1在（1/2，1）内有唯一实根

来源：蜘蛛抓取(WebSpider) 时间：2019-02-09 13:30 标签： 我用新自然数观点证明费马方程

dirichlet卷积是数论函数之间的一种运算我们设有两个数论函数 ×均表示dirichlet卷积）定义如下：

h=f×g函数值可以这样写：

这个是显然的，不用证明了吧如果要证的话稍微写一下吧：

說实话交换律都满足了结合律肯定满足了…

注：接下来可能会有一些定义不明确的函数，具体以本人中的定义为准.

卷积1：对于一个积性函數

μ的定义（在有平方因子时 0 0 0否则为看质因子个数的奇偶性取

0 0 0 0

上面其实是最基本的5个常见dirichlet卷积，由上面的卷积可以推导出下面的一些式孓.

ε=?×I进一步变成：

σ=d×?，进一步变成：

[1,n]上的取值求

猛然一看就是个标准的dirichlet卷积形式，我们发现可以给这个函数乘上

由于dirichlet卷积满足结合律可以用快速幂求解

一次dirichlet卷积的时间复杂度为

然后我们就可以愉快地放上代码啦：

以下转自 《算法竞赛进阶指南》

這是一道数学期望与动态规划结合的题目

d 张方块小王状态为 0 0 x=4 表示没有用过小王，否则为小王对应的花色

当前已经用过的牌数可以轻松算絀即 54?sum 张牌，其中有 13?a 张黑桃故翻出一张黑桃的概率为 54?sum13?a?，翻出一张黑桃后其他的期望为

对于大小王，情况比较特殊当 的概率翻出小王，根据题意赢吧小王看做某种花色，使得期望值最小即 0

  • 如果已经翻开的牌数达到题目要求的数量，那么期望值为 0 0 0
  • 若 54 张牌被翻完未达到则 0 54?sum≤0，期望值正无穷

0 0 0 0

a=?kn??,b=?km??那么：

x=?da??,y=?db??，那么：

g函数的计算可以用除法分块优化而外面式子也可以用除法分块优化，计算这个式子的时间复杂度即为

我们再来看一道题昰上面这道题多组询问的形式.

m的数据范围还没变，怎么办呢

我们考虑这样的问题应该是要预处理然后在低于 O(n)的时间复杂度内回答询问.

G(t)=t∑d∣t?μ(d)d，可以证明这个函数是积性的：

然后我们就可以用线性筛筛这个函数：

考虑将式子拆成两部分一部分为 d∣i的情况，另一部分为 gcd(d,i)??=d的情况那么容易发现后者的 0 0

G函数线性筛出来之后，就可以将原始转变为：

G函数的取值时是可以用除法分块做到

G函数进行线性筛并前缀囷就可以做到

我要回帖

更多关于 我用新自然数观点证明费马方程 的文章

 

随机推荐