AC. 梦想

数论目录下的文章

[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……
17/05/03 | 暂无评论 | 560阅读 阅读详情

[NOI 2016] 循环之美

题目描述 牛牛是一个热爱算法设计的高中生。在他设计的算法中,常常会使用带小数的数进行计算。牛牛认为,如果在k进制下,一个数的小数部分是纯循环的,那么它就是美的。 现在,牛牛想知道:对于已知的十进制数n和m,在k进制下,有多少个数值上互不相等的纯循环小数,可以用分数……
17/04/14 | 暂无评论 | 770阅读 阅读详情

[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……
16/06/02 | 暂无评论 | 545阅读 阅读详情

[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……
16/05/12 | 暂无评论 | 942阅读 阅读详情

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的过……
16/03/25 | 暂无评论 | 3,551阅读 阅读详情

数论相关线性筛

数论问题中,有许多函数需要我们进行线性预处理。利用欧拉筛法这个强大的算法,我们可以解决某些函数的线性筛。一般情况下,在数论题目中,如果我们要对一个函数线性筛,首先需要证明这个函数是积性函数。 积性函数是什么呢?在数论中,对于某函数f(x),若对任意两个互质的正整……
16/03/09 | 暂无评论 | 719阅读 阅读详情

[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组数据的结果。 题目解析 膜拜神……
16/03/03 | 暂无评论 | 2,431阅读 阅读详情

[BZOJ 1101] Zap

题目描述 FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x
16/01/04 | 暂无评论 | 659阅读 阅读详情

[BZOJ 1041] 圆上的整点

题目描述 求一个给定的圆x^2+y^2=r^2,在圆周上有多少个点的坐标是整数。 输入格式 正整数r \;(r \le 2 \times 10^9)。 输出格式 整点个数。 题目解析 题目十分清爽简洁,然而我WA了无数次…… 题目要求圆上的整点个数。首先坐标轴一定有4个点,其次四个象限的整点个数一定是相同……
15/12/20 | 暂无评论 | 1,101阅读 阅读详情

[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\;……
15/12/13 | 暂无评论 | 684阅读 阅读详情