费马大定理和勾股数

数论

  

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-12-11 14:49:34

额,总感觉忘了点什么,原来前面还有几个知识点没整理。。。。 大组合数: 这个式子算起来应该没难度把,当然阶乘谁不会算,那么问题来了如果n和m很大呢,那阶乘早爆了,所以就有了大组合数。 卢卡斯说: C(n, m) % p = C(n / p, m / p) * C(n%p, m%p) % p; 如果 C(n / p, m / p) 或C(n%p, m%p) 也太大呢? 卢卡斯说:…&h...

LinkLinkLink JZOJJZOJJZOJ 390939093909 DescriptionDescriptionDescription HintHintHint TrainTrainTrain ofofof ThoughtThoughtThought 将题目中的方程转化为 X≡Xax+cy≡bxdyX ≡ X^{ax+cy} ≡ b^xd^...

    1.所有因子个数 如果一个数是因数,就不断除这个数,保存这个因子次方的数 temp++; 运用所有因子个数计算公式(见上图),保存因子个数的 ans不断乘( temp+1 )。 注意 : 当最后,在 x 不断除因数得到的值有两种情况: x == 1,这说明 x 没有其他因子了。 x != 1, 这时 x 为其一个素数因子(且这个因子大于 根号x ),所以最后再乘(1+1...

P1582 倒水(洛谷)

数论

  

2019-12-24 01:45:15

只要求出的n转为二进制下,有k个1即可。 lowbit(n)取出非负整数n在二进制表示下最低位的1以及它后边的0构成的数值。 __builtin_popcountll(n)求出非负整数n在二进制表示下有几个1。 让n一直加lowbit(n),进位减少二进制表示下1的个数。...

ACM模版 描述 题解 首先求 p、qp、q 的最大公约数,为了在十进制下约分,此时我们先考虑十进制的情况什么条件才能有限,最简分数 abab 能化为有限小数的充要条件是分母 bb 不含有 22 和 55 以外的质因数,那么我们可以尝试猜一下,pqpq 在 bb 进制下想要有限的充要条件是 qq 不含 bb 拆解后的质因数以外的质因数。所以此时我们无需考虑 pp,只用不断去除 qq 中的 bb 的...

初见安~这里是传送门:洛谷P4841 城市规划 题解 这一类的问题好像还是挺常见的——给你n个不同的点,求可组成的无向连通图数。 【 我当然知道有两种解法啊,但我只会这一个QAQ】 设表示i个点的无向连通图数和i个点的无向图数。显然,,其中为i个点时的可选边数。 再来,对于我们还可以换一种表示:划分为有点1的集合和没有点1的集合,有点1的集合一定联通,另一个集合则随便,就有...

2018.5.23 T2前缀!

数论

  

2020-01-11 00:03:25

前缀! (b.cpp/c/pas) Time Limit:3 Sec Memory Limit:256 MB Description 那熙凤又问黛黛道:“我这有道题不知妹妹会不会做。”黛黛道:“且说。”熙凤笑道:“题目是这样的: 定义f0(x)=Ax,fn(x)= sigma[fn-1(i) |i<=x]。给出长度为N 的数组A(从...

洛谷·付公主的背包

数论

  

2020-01-13 07:17:36

初见安~这里是传送门:洛谷P4389 付公主的背包 题解 30%的数据明显我们可以暴力跑背包,但是大点点就不行了。我们考虑多项式。 根据母函数,我们对于每一种物品都可以写成一个多项式的形式,比如某物品大小为v,那么就有多项式: 对于n个物品,我们将他们每个的多项式都乘起来,所求就是最后那个多项式的前n项的系数。 但是这样做的复杂度是多少?,明显过不了。所以我们可能还要优化一下公式。 对于第i个物品...