标签: 数论

3 篇文章

有理多边形格点计数
本文原始论文:链接。 符号定义 $\lfloor x\rfloor$ 表示小于等于 $x$ 的最大整数;$\{x\}=x-\lfloor x\rfloor$,即 $x$ 的小数部分;$\%$ 表示取模。 线段上的格点数 如果你熟悉exgcd和线性同余方程,那么可以直接跳过本节。 定义1 设 $x_1,y_1,x_2,y_2$ 为有理数,定义 $L(…
AtCoder Beginner Contest 371题解
AtCoder Beginner Contest 371题解 E - I Hate Sigma Problems 定义函数 $f(l,r)$ 表示 $A[l],A[l+1],\cdots,A[r]$ 中不同的元素个数,求$$\sum_{i=1}^N\sum_{j=i}^N f(i,j).$$ 其实就是求数组 $A$ 中所有区间的元素种类数。可以通过…
黎曼zeta函数和素数分布的一个小结论
黎曼zeta函数和素数分布的一个小结论 今天发现了一个问题的巧妙解法,记录一下。 问题引入:任取两个自然数 $a,b$ ,求 $a,b$ 互质的概率。 设 $\gcd(a,b)=n$ 的概率为 $p(n)$ 。注意到 $\gcd(a,b)=n$ 的充要条件是 $n|a,n|b$ 并且 $\gcd(\frac{a}{n},\frac{b}{n})=1…