费马大定理和勾股数

数论

  

2019-06-14 03:06:34

大家都知道:若a^2 + b^2 = c^2,则(a,b,c)为一组勾股数,如(3,4,5);如果只给你一个数,你会怎么找到一组勾股数呢? 一.寻找勾股数: 若需要一組最小數為奇數的勾股數,可任意選取一個 3 或以上的奇數,將該數自乘為平方數,除以 2,答案加減 0.5 可得到 兩個新的數字,這兩個數字連同一開始選取的奇數,三者必定形成一組勾股數。但卻不一定是以這個選取數字為起首勾股 數的唯一可能...

牛客练习赛25A题-找规律

数论

  

2019-06-20 17:34:19

链接:https://www.nowcoder.com/acm/contest/158/A 来源:牛客网 题目描述 q次询问,每次给一个x,问1到x的因数个数的和。 输入描述: 第一行一个正整数q ; 接下来q行,每行一个正整数 x 输出描述: 共q行,每行一个正整数表示答案 示例1 输入 4 1 2 3 10 输出 1 3 5 27 说明 1的因数有1 2的因数有1,2 3的因数有1,3 以此类...

ACM模版 描述 题解 看到这个题,想到有一个叫做 Stern−BrocotStern−Brocot 树的东西,是专门用来拆分 0−10−1 所有真分数的,在《具体数学》上有讲,但是书没拿,也就能去仔细回顾一下了。 这个题只要答案,所以就算纯暴力也是可以搞定的,O(n2)O(n2) 枚举判断,不过这样不太优雅,所以考虑可以降低到 O(n)O(n),因...

「数学」数论只会gcd

数论

  

2019-10-29 09:36:04

题目链接 : https://www.luogu.org/problemnew/show/T33159 【题目背景】 小 Z 的 NOIP(节选)小 Z 的 NOIP(节选) 模拟只会猜题意 贪心只能过样例 数学上来先打表 DPDP 一般看规律 图论强行套模板 数论只会gcdgcd 递归递推伤不起 搜索茫然TLETLE 【题目描述】 可怜的蒟蒻小Z只会做gcd的水题。看,他翻开了一道例题: 求&s...

2019牛客暑期多校训练营(第一场)C 题解: 拉格朗日乘子法,首先引入拉格朗日乘子得出公式 f(x)=∑i=1n(pi−ai)2+2∗λ(∑i=0npi−1) f(x)=\sum_{i=1}^{n}(p_i-a_i)^2+2*\lambda(\sum_{i=0}^{n}p_i-1) f(x)=i=1∑n​(pi​&min...

FFTFFT前言 快速傅里叶变换 (fast Fourier transform),即利用计算机计算离散傅里叶变换(DFT)的高效、快速计算方法的统称,简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少,特别是被变换的抽样点数N越多,FFT算法计算量的节省就越显著。 FFT(Fast Fourier Trans...

快速幂

算法  数论

  

2019-09-29 13:27:54

首先看一道例题UVa 10006 题目大意是说对于任意的1<x<n1 < x < n1<x<n都有xn≡x(modn)x^n\equiv x(mod n)xn≡x(modn)成立的合数nnn称为Carmichael Number,对于给定的整数nnn,判断它是不是Carmichael Number 此题中,有n个待检查的数,如果每个数都按...

题解 不知道该叫啥 题目描述 【数据范围】 ​ n≤100,m≤109n \leq 100 , m \leq 10^9n≤100,m≤109 具体做法与心路历程 考场上首先想到的是O(nm)O(nm)O(nm)的做法。后来推不动了就去看后面的题,后面题也推不动了上了个厕所回来就想出来了。真的要充分利用。 还是太菜了,别人10min的切的题,我用了1h 具体做法 按照考试时的...

FFT学习笔记

FFT  数论

  

2019-11-04 21:07:20

FFT(Fast Fourier Transform) 快速傅里叶变换 引入 百度一下 这里的很多的工程上的文章和学术性的文章都是以音频和图像的处理和生活中的实际用途还有纯数学角度讲的,但是作为一个OIer,我们一般是不会用到这些的,所以这里就不讲解什么时域频域转换和波的分析之类的东西,而是将如何在OI中应用。 概念与前置 人物了解 傅里叶 其实这里要讲的傅里叶变换和完整的傅里叶变换有一定的区别,...

Fibonacci

数论  矩阵快速幂

  

2019-06-05 05:50:21

题目大意: 算第n个斐波那契数 解题思路: 根据题意来看就是一个矩阵快速幂的模板题,利用脑海中残留的快速幂知识然而忘了怎么算矩阵乘法,于是用人类最原始的暴力思维一个个枚举算了。。。所幸只是一个2×2的矩阵,然而还是算错了几步调试了半天。。还是要提高姿势水平啊。 暴力代码如下: 放个正规的标程吧,利用结构体算矩阵。 大佬初始化矩阵的方式就是骚。...

欧拉函数

欧拉  数论

  

2019-06-05 10:47:10

前言 欧拉函数φ(n)是小于n的正整数中与n互质的数的数目(φ(1)=1), φ(n)称为n的欧拉值 例如φ(8)=4(2,3,5,7)。 公式如下 φ(x)=x∏i=1n(1−1pi)\varphi (x)=x\prod_{i=1}^{n}(1-\frac{1}{p_i})φ(x)=x∏i=1n​(1−p...