给你一组形如下图的方程组： 
你需要解出最小的$x$。
有多组数据，每组数据以$n$开始，表示有$n$个方程组 接下来n行分别表示$a_1$，$m_i$
输出最小的$x$
这就是扩展中国剩余定理的模板题了。如果$m_i$都两两互质，那么就是直接中国剩余定理就好了。但这里$m_i$是随机的，所以要用到一些其他的处理手法。
这里我们可以先用扩展欧几里得求出第一组方程：$x+y*m_1=a_1$。这样，我们得到了一组通解$x=x_0+t*m_1$。我们利用这组通解带入第二组方程，得到：变形为：于是我们得到了另一个线性同余方程，并且可以解出$t$的通解。利用这个通解又可以代入下一个方程。于是我们可以这样推出整个方程的解。
用数学归纳法再严谨地说一遍做法：设已经求出了$k$组方程，$ m_0= \prod_{i=1}^{k} m_i$，前$k$组方程的通解为$x=x_0+t*m_0$。那么我们可以将通解代入第$k+1$组方程中，得到 再利用扩展欧几里得解出新方程的通解。于是，我们可以利用$n$次扩展欧几里得解出计算出答案。
1 |
|
我们要找出一个最小的 $L$ 的只由$8$构成的数，使它是$L$的整数倍。
由多组数据，每组数据一个数 $L$，输入以$0$结束 $L$($1≤L≤2000000000$)
一个数，表示数字的长度。如果不存在则输出$0$
一道比较玄学的题。这种只由一种数字构成相关问题都是一个套路吧。
先是将$8888…8$看成$(10^k-1)/9*8$。于是 $9L|8(10^k-1)$，等价为$10^k \equiv 1 (mod \frac{9L}{gcd(8, L)})$，这是一步特别重要的转化。
然后有这样的一个模型：若正整数$a, n$互质，那么满足$a^k \equiv 1 (mod n)$ 的最小正整数$k_0$一定是$ \varphi (n)$ 的约数。
因此，$k$一定为 $\varphi ( \frac{9L}{gcd(8, L)} ) $的约数。然后我们就可以枚举约数，再使用快速幂验证就OK了。有一个细节就是 $\varphi (n)$会大于MAX_INT所以要注意要再用快速乘防止爆$long long$。
1 |
|
给出正整数$n$和$k$，计算$G(n, k) =k \% 1 + k \% 2 + … + k \% n$的值。
输入仅一行，包含两个整数$n$, $k$ ($1<=n, k<=10^9$)
输出仅一行，即$j(n, k)$。
直接计算原式肯定是会T的。。。我们可以根据 $a \% b=a-\lfloor a/b \rfloor *b$ 将原式变形。所以答案可以在$n*k$的基础上减去上式的后一部分得到。然后我们可以发现 $\lfloor a/b \rfloor$ 的取值是一段一段的，所以可以对于每一段用等差数列求和的公式得出答案。
复杂度似乎是$O( \sqrt{n} )$的
1 |
|
对于任何正整数$x$，其约数的个数记作$g(x)$。如果某个正整数$x$满足：$g(x)>g(i)$ 其中$0<i<x$，则称x为反质数。现在给定一个数$N$你需要找出不大于$N$的最大反素数。
一个数$N$（$1<=N<=2000000000$）。
不超过N的最大的反质数。
其实我们要求的就是$1-N$内约数个数最多的数（如果个数一样就是小的那个），然后我们可以利用一些神奇的性质用搜索解出答案。
首先反素数的质因子是不会超过10个的，并且质因子的指数是单调递减的。利用这两个性质缩小搜索范围，然后直接dfs枚举它的质因子就好了。
1 |
|
我们定义素数的距离为两个相邻素数之间存在合数的个数。给你一个区间$[l, r]$你需要求出区间内距离最大和最小的两对素数
有多组数据，每组数据两个数l, r 其中l, r不超过2147483647，区间大小不超过1000000
如果不存在两个质数输出”There are no adjacent primes.” 否则输出 “x1,x2 are closest, y1,y2 are most distant.”其中x1,x2,y1,y2为两对距离最大和最小的素数
由于l, r都很大，所以不方便之间线性筛。但区间大小不超过1000000，所以我们要利用好这个条件。
由于区间较小，我们可以利用类似于筛的方法筛掉区间的合数。我们可以先预处理出$2^{16}$内的素数，对于每一个区间我们通过枚举素数$prime[i]$，把区间内为$prime[i]$的倍数标记。枚举了所有素数后，区间内没有标记的数就是素数了。然后$O(n)$扫一遍计算出答案。
1 |
|