whix

数论

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

/ 注册

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

Killer Names HDU - 6143

容斥定理的思想。当长度为n时，对于姓所用的字符个数从1~m-1讨论。 f[i]表示长度为n的姓用i个字符时，姓的可能数量。那么f[i] = in-c[i][i-1]*(i-1)n-c[i][i-2]*(i-2)^n… 因为要保证不重复，当用i个字符时，如果只用了i-1个，那么这种情况在只用i-1...

2019-08-24

0 420

The Balance POJ - 2142

拓展欧几里得的通解的应用；已知两个特解x0,y0, 通解 :x=x0+k*(b/gcd) y=y0-k*(a/gcd) 然后根据条件对一定范围内的解进行依次求解 #include <cstdio> #include <cstring> #include <cmath...

2019-08-19

0 468

C Looooops POJ - 2115

#include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; ll a,b,c,k; ll _gcd(ll a,ll b,ll &a...

2019-08-18

0 445

数论基础

1.最大公因数（ g c d gcd gcd...

2019-08-18

0 343

GCD XOR UVA - 12716

题目一开始看，完全没有思路。看了书上的分析才会，而且枚举过程一开始也写错了。本题主要是利用性质，如果gcd(a,b)==a^b=c,那么b=a-c。（书上有证明,打表可以看出），然后主要枚举a ,c即可。枚举的方法借鉴与素数筛法，减小时间复杂度。（一开始不会），同时利用递推的关系先预处理出每个n...

2019-08-18

0 408

Minimum Sum LCM UVA - 10791

数论题，唯一分解定理的应用把每个n分解成素数的幂的表示形式，把相同的素因子放在一起时，有最小和。特殊情况： n=1时，只有一个素因子时，列素数时，只需列一部分即可，如果最后无法分解，表示最后剩下的数即为素数。 pow有精度损失，自己手写。 #include <cstdio> ...

2019-08-18

0 413

Choose and divide UVA - 10375

求两个组合数的商，数据大，肯定不能直接算。根据唯一分解定理，每个数可以分解成若干个素数的幂的乘积的形式。可以把分解成的素数的幂记下来，最后知道每个素数的出现次数，依次求幂即可。主要的收获： 1.学会用唯一分解定理 2.复习了欧拉筛 3.pow()的函数原型：double pow(double,d...

2019-08-18

0 514