给出 $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$ 取模。

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

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

一个函数 $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$。

定义欧拉函数的变种

$$\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}$$

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

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

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

求

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

$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$ 的余数就可以了。

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

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

求其第 $n$ 项。

求

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

链接

BZOJ 3028

链接

UOJ 221
BZOJ 4652
LOJ 2085

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$ 的平方之和是多少。

有 $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$ 不相交（即没有公共点）。

问题很简单，已知 $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)$ 的和。

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

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).

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

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)的最小非负整数。

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.

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?

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

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?

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.

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.

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.

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.

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.

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).

请计算 $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]$。

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

链接

bzoj2179

输入

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

输出

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

组合数表示的是从 $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$ 的倍数。

三角形面积

题目描述

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