数论目录下的文章
[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 1101] Zap
题目描述
FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x
[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\;……