Description

题目链接：BZOJ 3813

在一片美丽的大陆上有 $100000$ 个国家，每个国家有一个银行。某大公司的领袖在这 $100000$ 个银行开户时都存了 $3$ 大洋，他惜财如命，因此会不时地派小弟 GFS 清点一些银行的存款或者让 GFS 改变某个银行的存款。这里发行的软妹面额是最小的 $60$ 个素数，任何人的财产都只能由这 $60​$ 个基本面额表示。

领袖习惯将一段编号连续的银行里的存款拿到一个账房去清点。如果领袖选择清点编号在 $[a,b]$ 内的银行财产，他会先对 $[a,b]$ 的财产求和（计为 $\text{product}$），然后在编号属于 $[1,\text{product}]$ 的账房中选择一个去清点存款。一个账房 $\text{number}$ 可能被选中当且仅当 $\gcd(\text{product},\text{number})=1$。当领袖又赚大钱了的时候，他会在某个银行改变存款，但是领袖不会在某个银行的存款总数超过 $10^6$。

现在 GFS 预先知道了领袖的清点存款与变动存款的 $x$ 次计划，想请你告诉他，每次清点存款时领袖有多少个账房可以供他选择，当然这个值可能非常大，GFS 只想知道对 $19961993$ 取模后的答案。

数据范围：$1\le x\le 10^5$

Description

题目链接：Luogu 5179

给你四个正整数 $a,b,c,d$，求一个最简分数 $\frac{p}{q}$ 满足 $\frac{a}{b}<\frac{p}{q}<\frac{c}{d}​$。

若有多组解，输出 $q$ 最小的一组，若仍有多组解，输出 $p$ 最小的一组。数据保证至少存在一个最简分数符合条件。

本题 $T$ 组数据。

数据范围：$1\le T\le 500$，$1\le a,b,c,d\le 10^9$

Description

题目链接：Codeforces 724C

有一个 $n\times m$ 的矩形，四周有围墙围起来，其左上角和右下角的坐标分别为 $(0,0)$ 和 $(n,m)$。从 $(0,0)$ 开始以 $\sqrt 2$ 个单位每秒的速度向 $(1,1)$ 的方向发射一束光线，每次遇到墙都正常反射（符合物理的反射），光线射到顶点会被吸收。在这个矩形内有 $k$ 个点，坐标分别为 $(x_i,y_i)$，求每个点第一次被光线经过的时刻。

数据范围：$2\le n,m\le 10^5$，$1\le k\le 10^5$，$1\le x_i<n$，$1\le y_i<m$

Description

题目链接：HDU 1299

求解如下丢番图方程的正整数解个数：

$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\quad (x,y,n\in\mathbb{N}^+,x\le y)$$

本题 $T$ 组数据。

数据范围：$1\le n\le 10^9$

Description

题目链接：BZOJ 2705

Longge 的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数 $n$，你需要求出：

$$\sum_{i=1}^n\gcd(i,n)$$

数据范围：$1\le n\le 2^{32}​$

Description

题目链接：BZOJ 2749

艾利欧在她的被子上发现了一个数字 $n$，她觉得只要找出最小的 $x$ 使得，$\varphi^x(n)=1$。根据这个 $x$ 她就能找到曾经绑架她的外星人的线索了。现在她给你这个数字 $n$ 的标准分解形式 $n=\prod_{i=1}^m {p_i}^{q_i}$，请你帮助她算出最小的 $x$。

本题 $T$ 组数据。

数据范围：$1\le T\le 50$，$1\le p_i\le 10^5$，$1\le q_i\le 10^9$

Description

题目链接：BZOJ 3884

求如下式子的值：

$$2^{2^{2\cdots}}\bmod p$$

本题 $T$ 组数据。

数据范围：$1\le T\le 1000$，$1\le p\le 10^7$

Description

题目链接：BZOJ 2186

大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为 $[1,n!]$，但是，政府只发行编号与 $m!$ 互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对 $R$ 取模后的答案即可，保证 $R​$ 是一个质数。

本题 $T$ 组数据。

数据范围：$1\le T\le 10^4$，$1\le R\le 10^9+10$，$1\le m\le n\le 10^7$

欧拉函数是数论中的一个重要积性函数。

Description

题目链接：BZOJ 2818

给定整数 $n$，求 $1\le x,y\le n$ 且 $\gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对。

数据范围：$1\le n\le 10^7​$