whix

数论

acm(1) codeforces(13) dp(1) java(1) 区域赛真题(2) 图论(20) 字符串(3) 数据结构(4) 未归档(32) 牛客(8) 组合数学(7) 计算几何(1) 题解(9)

/ 注册

全部文章 / 数论（共37篇）

Number Sequence POJ - 1019

大概思路：用前缀和预处理出，当以某一个数为结尾数字时，前面的全部数字的总位数，只要处理到31268即可满足题目的要求。然后根据题目要求的位数，判断这个位置处于哪一段，然后遍历即可找到对应的数字。 #include <cstdio> #include <cstring> ...

2019-10-09

0 549

Harmonic Number (II) LightOJ - 1245（数论基础！）

***解！ #include <bits/stdc++.h> using namespace std; typedef long long ll; int n; ll res; int main() { int t,cas=0; scanf("%d"...

2019-10-08

0 392

Strange Optimization

题目意思是要求在t固定的情况下，i，j任意取值，求得f(t)的所有最小值中的最大值。对于i/n-j/m而言，根据拓展欧几里得的有解的条件，那么它可以表示gcd(n,m)/(nm)的任意倍数，那么当t是固定的时，t到和它最近的两个gcd(n,m)/(nm)的倍数之间的距离中的最小值必然小于等于gcd...

2019-10-04

0 501

求一个大数的前3位和后3位

求后3位，快速幂取模求前3位：对于n^k这个数，可以用10 ^p表示（p为浮点数），即10^p=n ^k, 那么p=k*log10(n) 用整型数x表示p的整数部分，用浮点数y表示p的小数部分，0<=y<1。那么10^p=10 ^(x+y)=(10 ^y) * (10 ^x)。即...

2019-10-04

0 343

Prime Independence LightOJ - 1356

HK+质因子分解 HK是二分图匹配中匈牙利算法的优化，时间复杂度O(sqrt(n)*m) 先通过bfs寻找多条增广路，记下每个点到源点的距离（类似于网络流dinic算法），然后用类似于匈牙利算法中dfs的方法，进行匹配。要求图是二分的，并且根据增广路的特性模板： #include<bit...

2019-10-02

0 495

Big Number HDU - 1018

题解的方法确实让我大开眼界。求n!的位数。方法1：求10^m>=n!,的最小m值。 =log10(n!)=log10(n)+log10(n-1)+log10(n-2)+…+log10(1)。为了保存精度，答案用double存，最后数据类型转换并+1。double转int向下取整。 #...

2019-09-25

0 443

线性方程组+高斯消元

作用： 1.解n元一次线性方程组 2.可以用来求矩阵的秩 3.求可逆方阵的逆矩阵其本质就是通过初等行变换，把线性方程组的增广矩阵化为行阶梯型矩阵。未优化的高斯消元：（顺序消去法）基本思想：目标就是把系数矩阵的增广矩阵通过初等行变换一步一步的转化为行阶梯型矩阵，然后从后到前把已求出的解代入前面的...

2019-09-16

0 522

因子和与因子个数，求逆元的通用方法

先上公式：因子和: 如果p为素数，a为整数，那么p^a 的因子和为 1 + p + p^2 + p ^3+…+p ^a=(p ^(a+1) - 1)/(p-1);(等比数列求和) 如果对于对于一个整数数 n,可以进行质因数分解成 p1^a1 * p2 ^a2 p3 ^a3…pk ^ak 那么因子和...

2019-09-11

0 1270

指数循环节

题集 hdu 4335 总的思想：暴力 ep=euler§ 1.第一部分当n!<ep时，直接算n^(n!)的取值。 2第二部分当n<ep&&n!<ep时，利用欧拉降幂，求解。 3第三部分n>=ep时,那么根据欧拉降幂，指数固定为ep,式子变成n^ep,只有n变...

2019-09-10

0 470

多项式

多项式的gcd: uva 10951

2019-09-06

0 302