标签: 数论

「CodeForces 1254B」Send Boxes to Alice

This is the harder version of the problem. In this version, 1≤𝑛≤106 and 0≤𝑎𝑖≤106. You can hack this problem if you locked it. But you can hack the previous problem only if you locked both problems

Christmas is coming, and our protagonist, Bob, is preparing a spectacular present for his long-time best friend Alice. This year, he decides to prepare 𝑛 boxes of chocolate, numbered from 1 to 𝑛. Initially, the 𝑖-th box contains 𝑎𝑖 chocolate pieces.

「NewCode 2019-3」 E. Big Integer

For little pupils, a very large number usually means an integer with many many digits. Let's define a class of big integers which consists only of the digit one (111)(11 \cdots 1). The first few integers in this class are 1,11,111,11111, 11, 111, 1111 \cdots. Denote A(n)A(n) as the nn-th smallest integer in this class. To make it even larger, we consider integers in the form of A(ab)A(a^b)
. Now, given a prime number pp , how many pairs (i,j)(i, j) are there such that 1 in, 1jm, A(ij)0(mod p)\leq i \leq n,\ 1 \leq j \leq m,\ A(i^j) \equiv 0(mod \ p)

「LightOJ 1336」 Sigma Function

Sigma function is an interesting function in Number Theory. It is denoted by the Greek letter Sigma (σ). This function actually denotes the sum of all divisors of a number. For example σ(24) = 1+2+3+4+6+8+12+24=60. Sigma of small numbers is easy to find but for large numbers it is very difficult to find in a straight forward way. But mathematicians have discovered a formula to find sigma. If the prime power decomposition of an integer is

「SDOI2010」 古代猪文

猪王国的文明源远流长,博大精深。

iPig在大肥猪学校图书馆中查阅资料,得知远古时期猪文文字总个数为N。当然,一种语言如果字数很多,字典也相应会很大。当时的猪王国国王考虑到如果修一本字典,规模有可能远远超过康熙字典,花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然,猪王国的文字后来随着历史变迁逐渐进行了简化,去掉了一些不常用的字。

「NOIP2009」 HanKson的趣味题

Hanks 博士是 BT(Bio-Tech,生物技术) 领域的知名专家,他的儿子名叫 Hankson。现在,刚刚放学回家的 Hankson 正在思考一个有趣的问题。

今天在课堂上,老师讲解了如何求两个正整数 c1c_1c2c_2 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识,他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”,这个问题是这样的:已知正整数a0,a1,b0,b1a_0,a_1,b_0,b_1 ,设某未知正整数 x 满足:

「POJ 2773」 Happy 2006

Two positive integers are said to be relatively prime to each other if the Great Common Divisor (GCD) is 1. For instance, 1, 3, 5, 7, 9...are all relatively prime to 2006.

「CF 1152C」 Neko does Maths

Neko loves divisors. During the latest number theory lesson, he got an interesting exercise from his math teacher.

Neko has two integers 𝑎 and 𝑏. His goal is to find a non-negative integer 𝑘 such that the least common multiple of 𝑎+𝑘 and 𝑏+𝑘 is the smallest possible. If there are multiple optimal integers 𝑘, he needs to choose the smallest one.