数论目录下的文章
[CQOI 2017] 小Q的表格
题意简述
有一个表格，表格有无穷多行，无穷多列，行和列都从1开始标号。
表格里面每个格子都填了一个整数，第a行第b列的整数记为f(a,b)。
这个表格要满足一些条件：
1. 对任意的正整数a,b,都要满足f(a,b)=f(b,a)；
2. 对任意的正整数a,b，都要满足b \times f(a,a+b)=(a+b) \tim……
[NOI 2016] 循环之美
题目描述
牛牛是一个热爱算法设计的高中生。在他设计的算法中，常常会使用带小数的数进行计算。牛牛认为，如果在k进制下，一个数的小数部分是纯循环的，那么它就是美的。
现在，牛牛想知道：对于已知的十进制数n和m，在k进制下，有多少个数值上互不相等的纯循环小数，可以用分数……
[BZOJ 2956] 模积和
题目描述
求\sum_{i=1}^{n} \sum_{j=1}^{m} {(n \mod i)(m \mod j)[i \neq j]}
输入格式
两个整数n,m。
1 \le n,m \le 10 ^ 9
输出格式
一个整数表示答案\mod 19940417的值。
题目解析
我们先不考虑i = j的情况。由分配律原式可转化为(\sum_{i=1}^{n} {n \mod i})(\sum_{i=1}^{m……
[NOIP 2014] 解方程
题目描述
已知多项式方程：
a_0+a_1x+a_2x^2+...+a_nx^n=0
求这个方程在[1,m]内的整数解（n和m均为正整数）。
输入格式
第一行包含2个整数n,m，每两个整数之间用一个空格隔开。
接下来的n+1行每行包含一个整数，依次为a_0,a_1,a_2,...,a_n。
0 \lt n \le 100,|a_i| \le 10^{1000……
GCD黑科技
来看这样一个问题：
有T组询问，第i组询问给出两个正整数a_i,b_i。对于每组询问，求\gcd(a_i,b_i)。1 \le T \le 10 ^ 7,1 \le a_i,b_i \le 10 ^ 7。
对于一般题目，求一次\gcd(a,b)的时间是\log(n)。但是，在可以预处理的情况下，即a,b是两个在一定范围内的整数时，求\gcd的过……
数论相关线性筛
数论问题中，有许多函数需要我们进行线性预处理。利用欧拉筛法这个强大的算法，我们可以解决某些函数的线性筛。一般情况下，在数论题目中，如果我们要对一个函数线性筛，首先需要证明这个函数是积性函数。
积性函数是什么呢？在数论中，对于某函数f(x)，若对任意两个互质的正整……
[BZOJ 2693] JZPTAB
题目描述
计算\sum_{i=1}^{n} \sum_{j=1}^{m} {lcm (i,j)} \mod (10^8 + 9)，有多组数据。
输入格式
一个正整数T表示数据组数。
接下来T行 每行两个正整数 表示N、M。（T <= 10000；N, M<=10000000）
输出格式
共T行，每行一个整数 表示第i组数据的结果。
题目解析
膜拜神……
[BZOJ 1041] 圆上的整点
题目描述
求一个给定的圆x^2+y^2=r^2，在圆周上有多少个点的坐标是整数。
输入格式
正整数r \;(r \le 2 \times 10^9)。
输出格式
整点个数。
题目解析
题目十分清爽简洁，然而我WA了无数次……
题目要求圆上的整点个数。首先坐标轴一定有4个点，其次四个象限的整点个数一定是相同……
[XJOI] 方程趣题
题目摘要
求解下列方程正整数解(x,y)对数：
\frac{1}{{N!}} = \frac{1}{x} + \frac{1}{y}\;{\rm{(}}1 < = N < = {10^4},x,y \in {N^*})
题目解析
这种题目初看没有什么思路，搜索不太可做。那么换用数学方法试试。
令m = N! 。观察上式，发现x和y必定大于m，不妨设x = m + k\;……
[SDOI 2016] 生成魔咒
[BZOJ 2754] 喵星球的点名
[BZOJ 1187] 神奇游乐园
[BZOJ 3931] 网络吞吐量