「LOJ 138」类欧几里得算法

给出 $T$ 组询问,每组用 $n, a, b, c, k_1, k_2$ 来描述。对于每组询问,请你求出

$$
\sum_{x = 0} ^ {n} x ^ {k_1} {\left \lfloor \frac{ax + b}{c} \right \rfloor} ^ {k_2}
$$

对 $1000000007$ 取模。

「CC SQRGOOD」Simplify the Square Root-杜教筛 + 二分

求第 $n$ 个含有大于 $1$ 的平方因子的数。

「BZOJ 1143/2718」毕业旅行-Dilworth 定理

一个 $n$ 个点 $m$ 条边的有向图,求最多能选择多少个点,使得任意两点不连通。

「LOJ 6053」简单的函数-ExtendedEratosthenesSieve

一个函数 $f(x)$,它满足:

  1. $f(1) = 1$。
  2. $f(p ^ c) = p \oplus c$($p$ 为质数,$\oplus$ 表示异或)。
  3. $f(ab) = f(a)f(b)$($a$ 与 $b$ 互质)。

求 $\sum\limits_{i = 1} ^ n f(i) \bmod 1000000007$。

「SuperOJ 1297」数学题-ExtendedEratosthenesSieve

定义欧拉函数的变种
$$\phi(n, d) = \prod_{k = 1} ^ m (p_k ^ {e_k} + d)$$
特别的,$\phi(1, d) = 1$,求
$$\sum_{i = 1} ^ n \phi(i, d) \pmod {10 ^ 9 + 7}$$

「BZOJ 4916」神犇和蒟蒻-ExtendedEratosthenesSieve

求 $A = \sum\limits_{i = 1} ^ n \mu(i ^ 2), B = \sum\limits_{i = 1} ^ n \varphi(i ^ 2)$

「SPOJ DIVCNT[2/3/k]」-ExtendedEratosthenesSieve

求 $\sum\limits_{i = 1} ^ n \sigma_{0}(i ^ k)$,$n, k \leq 10 ^ {10}, T \leq 10000$。

「BZOJ 5104」Fib数列-BSGS+二次剩余

求在 $\bmod 10 ^ 9 + 9$ 的意义下,数字 $C$ 在 $\text{Fib}$ 数列的哪个位置,无解输出 $-1$。

「BZOJ 3453」XLkxc-拉格朗日插值


$$\sum_{i=0}^{n} \sum_{j=1}^{a+i \times d} \sum_{l=1}^{j}l^k$$

「BZOJ 4559」成绩比较-拉格朗日插值

$G$ 系共有 $n$ 位同学,$M$ 门必修课。这 $N$ 位同学的编号为 $0$ 到 $N - 1$ 的整数,其中 $B$ 神的编号为 $0$号。这 $M$ 门必修课编号为 $0$ 到 $M - 1$ 的整数。一位同学在必修课上可以获得的分数是 $1$ 到 $U_i$ 中的一个整数。如果在每门课上 $A$ 获得的成绩均小于等于 $B$ 获得的成绩,则称 $A$ 被 $B$ 碾压。在 $B$ 神的说法中,$G$ 系共有 $K$ 位同学被他碾压(不包括他自己),而其他 $N-K-1$ 位同学则没有被他碾压。$D$ 神查到了 $B$ 神每门必修课的排名。这里的排名是指:如果 $B$ 神某门课的排名为 $R$,则表示有且仅有 $R-1$ 位同学这门课的分数大于 $B$ 神的分数,有且仅有 $N-R$ 位同学这门课的分数小于等于 $B$ 神(不包括他自己)。我们需要求出全系所有同学每门必修课得分的情况数,使其既能满足B神的说法,也能符合 $D$ 神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。你不需要像 $D$ 神那么厉害,你只需要计算出情况数模 $10 ^ 9 + 7$ 的余数就可以了。

「51NOD 1195」斐波那契数列的循环节-二次剩余

求斐波那契数列 $\text{mod }n$ 的循环节长度。

常系数齐次线性递推

$h_n = a_1h_{n - 1} + a_2h_{n - 2} + \cdots + a_kh_{n - k}$

求其第 $n$ 项。

「BZOJ 4176」Lucas的数论-莫比乌斯反演+杜教筛


$$\sum_{i = 1} ^ n\sum_{j = 1} ^ nd(ij)$$

「BZOJ 3028」食物-生成函数

链接

BZOJ 3028

「BZOJ 2813」奇妙的 Fibonacci-线性筛

Fibonacci 数列是这样一个数列:
$F_1 = 1, F_2 = 2, F_3 = 3 \cdots$ $F_i = F_{i - 1} + F_{i - 2}$ (当 $i \geq 3$)
pty 忽然对这个古老的数列产生了浓厚的兴趣,他想知道:对于某一个 Fibonacci 数 $F_i$,有多少个 $F_j$ 能够整除 $F_i$ ($i$ 可以等于 $j$),他还想知道所有 $j$ 的平方之和是多少。

「BJ模拟」「HDU-5852」Intersection is not allowed!

有 $K$ 个棋子在一个大小为N×N的棋盘。一开始,它们都在棋盘的顶端,它们起始的位置是 $(1, a_1),(1, a_2),…,(1, a_k)$,它们的目的地是 $(n, b_1), (n, b_2),…,(n, b_k)$。

一个位于 $(r,c)$ 的棋子每一步只能向右走到 $(r, c + 1)$ 或者向下走到 (r + 1, c)$。

我们把 $i$ 棋子从 $(1, a_i)$ 走到 $(n, b_i)$ 的路径记作 $p_i$。

你的任务是计算有多少种方案把 $n$ 个棋子送到目的地,并且对于任意两个不同的棋子 $i,j$,使得路径 $p_i$ 与 $p_j$ 不相交(即没有公共点)。

「BJ模拟」简单精暴的题目-二项式定理

问题很简单,已知 $n, k, s(l)$,$\forall i \in N^+, i \leq n$,求 $\sum\limits_{j = 1}^i (\sum\limits_{l = j}^i s(l))^k) \text{ mod } 1000000007$。
即求:


$\sum\limits_{j = 1}^1 (\sum\limits_{l = j}^1 s(l))^k) \text{ mod } 1000000007$
$\sum\limits_{j = 1}^2 (\sum\limits_{l = j}^2 s(l))^k) \text{ mod } 1000000007$
$\cdots$
$\sum\limits_{j = 1}^n (\sum\limits_{l = j}^n s(l))^k) \text{ mod } 1000000007$

共 $n$ 个数,其中 $\sum\limits_{i = a}^b f(i)$ 表示 $f(a) + \cdots + f(b)$ 的和。

「HNOI2004」「BZOJ1213」高精度开根-高精度+牛顿法

晓华所在的工作组正在编写一套高精度科学计算的软件,一些简单的部分如高精度加减法、乘除法早已写完了,现在就剩下晓华所负责的部分:实数的高精度开m次根。因为一个有理数开根之后可能得到一个无理数,所以这项工作是有较大难度的。现在要做的只是这项工作的第一步:只对自然数进行开整数次根,求出它的一个非负根,并且不考虑结果的小数部分,只要求把结果截断取整即可。程序需要根据给定的输入,包括需要开根的次数,以及被开根的整数;计算出它的非负根取整后的结果。

「POJ-2720」Last Digits-欧拉函数

Exponentiation of one integer by another often produces very large results. In this problem, we will compute a function based on repeated exponentiation, but output only the last n digits of the result. Doing this efficiently requires careful thought about how to avoid computing the full answer.

Given integers b, n, and i, we define the function f(x) recursively by f(x) = b f(x-1) if x > 0, and f(0)=1. Your job is to efficiently compute the last n decimal digits of f(i).

「BZOJ-2242」计算器-BSGS

你被要求设计一个计算器完成以下三项任务:

1,给定y,z,p,计算Y^Z Mod P 的值;

2,给定y,z,p,计算满足xy≡ Z ( mod P )的最小非负整数;

3,给定y,z,p,计算满足Y^x ≡ Z ( mod P)的最小非负整数。

「POJ-1284」Primitive Roots-原根+欧拉函数

We say that integer x, 0 < x < p, is a primitive root modulo odd prime p if and only if the set { (xi mod p) | 1 <= i <= p-1 } is equal to { 1, …, p-1 }. For example, the consecutive powers of 3 modulo 7 are 3, 2, 6, 4, 5, 1, and thus 3 is a primitive root modulo 7.
Write a program which given any odd prime 3 <= p < 65536 outputs the number of primitive roots modulo p.

「POJ-3243」Clever Y-BSGS

Little Y finds there is a very interesting formula in mathematics:

$X^Y$ mod $Z = K$

Given X, Y, Z, we all know how to figure out K fast. However, given X, Z, K, could you figure out Y fast?

「BZOJ-1876」SuperGCD-高精度

Sheng bill有着惊人的心算能力,甚至能用大脑计算出两个巨大的数的GCD(最大公约 数)!因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你,并要求和你比 赛,但是输给Sheng bill岂不是很丢脸!所以你决定写一个程序来教训他。

「POJ-2891」Strange Way to Express Integers-扩展欧几里德

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:
Choose k different positive integers a1, a2, \cdots , ak. For some non-negative m, divide it by every ai (1 \leq i \leq k) to find the remainder ri. If a1, a2, \cdots , ak are properly chosen, m can be determined, then the pairs (ai, ri) can be used to express m.

“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”

Since Elina is new to programming, this problem is too difficult for her. Can you help her?

「POJ-1006」Biorhythms-中国剩余定理

Some people believe that there are three cycles in a person’s life that start the day he or she is born. These three cycles are the physical, emotional, and intellectual cycles, and they have periods of lengths 23, 28, and 33 days, respectively. There is one peak in each period of a cycle. At the peak of a cycle, a person performs at his or her best in the corresponding field (physical, emotional or mental). For example, if it is the mental curve, thought processes will be sharper and concentration will be easier.

「POJ-2115」C Looooops-扩展欧几里德

A Compiler Mystery: We are given a C-language style for loop of type
for (variable = A; variable != B; variable += C)

statement;

I.e., a loop which starts by setting variable to value A and while variable is not equal to B, repeats statement followed by increasing the variable by C. We want to know how many times does the statement get executed for particular values of A, B and C, assuming that all arithmetics is calculated in a k-bit unsigned integer type (with values 0 <= x < 2 k) modulo 2 k.

「CF-527A」Playing with Paper-模拟

One day Vasya was sitting on a not so interesting Maths lesson and making an origami from a rectangular a mm  ×  b mm sheet of paper (a > b). Usually the first step in making an origami is making a square piece of paper from the rectangular sheet by folding the sheet along the bisector of the right angle, and cutting the excess part.

「POJ-3090」Visible Lattice Points-欧拉函数

A lattice point (x, y) in the first quadrant (x and y are integers greater than or equal to 0), other than the origin, is visible from the origin if the line from (0, 0) to (x, y) does not pass through any other lattice point. For example, the point (4, 2) is not visible since the line from the origin passes through (2, 1). The figure below shows the points (x, y) with 0 \leq x, y \leq 5 with lines from the origin to the visible points.

「POJ-3421」X-factor Chains-质因数分解

Given a positive integer X, an X-factor chain of length m is a sequence of integers,

$1 = X_0, X_1, X_2, \cdots , X_m = X$

satisfying

$X_i < X_i+1$ and $X_i | X_i+1$ where a | b means a perfectly divides into b.

Now we are interested in the maximum length of X-factor chains and the number of chains of such length.

「POJ-2689」Prime Distance-线筛

The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by 1 and itself). The first prime numbers are 2,3,5,7 but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, 2,3 are the only adjacent primes that are also adjacent numbers.
Your program is given 2 numbers: L and U (1<=L< U<=2,147,483,647), and you are to find the two adjacent primes C1 and C2 (L<=C1< C2<=U) that are closest (i.e. C2-C1 is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L<=D1< D2<=U) where D1 and D2 are as distant from each other as possible (again choosing the first pair if there is a tie).

「BZOJ-2194」快速傅立叶之二-FFT

请计算 $C[k]=\sum(a[i]*b[i-k])$ 其中 $k \leq i < n$ ,并且有 $n \leq 10 ^ 5$。 $a,b$ 中的元素均为小于等于 $100$ 的非负整数。

链接

bzoj2194

输入

第一行一个整数 $N$ ,接下来 $N$ 行,第 $i+2 \cdots i+N-1$ 行,每行两个数,依次表示$a[i],b[i]$ $(0 \leq i < N)$。

输出

输出 $N$ 行,每行一个整数,第 $i$ 行输出 $C[i-1]$。

「BZOJ-2179」FFT快速傅立叶-FFT

给出两个 $n$ 位 $10$ 进制整数 $x$ 和 $y$,你需要计算 $x \times y$。

链接

bzoj2179

输入

第一行一个正整数 $n$。 第二行描述一个位数为 $n$ 的正整数 $x$。 第三行描述一个位数为 $n$ 的正整数 $y$。

输出

输出一行,即 $x \times y$ 的结果。

「NOIP2016」组合数问题 - 递推 + 前缀和

组合数表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子,从 $(1, 2, 3) $ 三个物品中选择两个物品可以有 $(1, 2)$, $(1, 3)$, $(2, 3)$ 这三种选择方法。
根据组合数的定义,我们可以给出计算组合数的一般公式:
$C_n ^ m = \frac{n!}{m!(n - m)!}$
其中 $n! = 1 \times 2 \times \cdots \times n$。
小葱想知道如果给定 $n$, $m$ 和 $k$,对于所有的 $0 \leq i \leq n$, $0 \leq j \leq \min(i, m)$ 有多少对 $(i, j)$ 满足是 $k$ 的倍数。

「SuperOJ 214」三角形面积

三角形面积

题目描述

如果知道三角形的三边长a ,b ,c ,我们就可以求出该三角形周长的一半 ,进一步使用公式:
计算出该三角形的面积。这个求面积的公式就是著名的海伦公式。
给你三个正实数,如果这三个实数分别作为边长能构成一个三角形,则请你求出这个三角形的面积并输出;如果不能构成三角形,请输出“No.” ,注意引号不能输出。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×