青蛙的约会
Description
青蛙A和青蛙B住在同一条纬度线上，规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。 设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。 现在要你求出它们跳了几次以后才会碰面（即两只青蛙在同一时间跳到同一点上）。
Input
输入只有一行：5个整数x，y，m，n，L，
其中x \neq y<2e9，0
Output
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"。
Sample Input
1 2 3 4 5
Sample Output
4
Analysis
假设时间t后相遇，那么此时青蛙A的坐标为x^{‘}=(x+tm)\%L，青蛙B的坐标为y^{‘}=(y+tn)\%L。 且有x^{‘}=y^{‘}，即：
x+tm \equiv y+tn(mod \; L) t(m-n) \equiv y-x(mod \; L)
令a=m-n，x=t，b=y-x，m=L， 该问题变为求解一次同余方程$ax \equiv b(mod \; m)(m > 0)$。 请注意，在正式求解前，我们需要进行如下变换：
$a = (a \% m + m) \% m$，$b = (b \% m + m) \% m$，
即将$a$和$b$映射到$[0, m)$的非负数区间上，这样做是为了保证接下来求得的$a$和$b$的公约数为正数（为什么$\gcd(a, m)$要求是正数？下面再说），且在模$m$的条件下解$x$不变。
令$d=\gcd(a, m)$，先给出两个定理：
定理1：若d \nmid b，则该方程无解。
定理2：若d \mid b，则该方程有d个解。 并且，若\alpha x \equiv \beta (mod \; m^{‘})的唯一最小正整数解为r， 那么，ax \equiv b(mod \; m)的d个解为 { x | r + km^{‘} },k=0,1…d-1 其中\alpha=\frac{a}{d},\beta=\frac{b}{d},m^{‘}=\frac{m}{d}。
注意到*：*解的间隔为\frac{m}{d}，那么最小正整数解一定有r \in [0, \frac{m}{d})。
至于证明，将在文章的末尾给出。
对于计算机来说，定理1和2可以结合计算，具体如下：
利用exgcd扩展欧几里得算法可得d=exgcd(a, m, x, y)，其中d = \gcd(a, m)， 即\quad \exists x, y \; \mathrm{s.t.} \;ax + my = d， \qquad ax \equiv d(mod \; m)， 那么ax \cdot \frac{b}{d} \equiv d \cdot \frac{b}{d}(mod \; m)， 即\quad a \cdot (x \cdot \frac{b}{d})\equiv b(mod \; m)， 令x^{‘}=x \cdot \frac{b}{d}，
那么x^{‘}就是我们最终要得到的解了！ 吗？当然不是！！！
请注意*：*采用exgcd算法得到的系数x有可能是负的， 由于b和d是非负的（对应了上文为什么要求 d是正数）， 所以x^{‘}有可能是负的，由定理2可知，令t = \frac{m}{d}， 最小正整数解应为(x^{‘} \% t + t) \% t。
至此，终于完成对本题的分析，相信你一定能够写出代码，参考代码如下。
Code
#include <iostream>
#include <algorithm>
#define endl "\n"
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL m, LL &x, LL &y) {
if(m == 0) {
x = 1;
y = 0;
return a;
}
LL _x, _y;
LL d = exgcd(m, a % m, _x, _y);
x = _y;
y = _x - a / m * _y;
return d;
}
int main() {
LL x, y, m, n, L;
cin >> x >> y >> m >> n >> L;
LL a = ((m - n) % L + L) % L;
LL b = ((y - x) % L + L) % L;
m = L;
int d = exgcd(a, L, x, y);
LL t = L / d;
if(b % d) puts("Impossible");
else cout << (x * (b / d) % t + t) % t << endl;
return 0;
}
证明
定理一：若d∤b，则该方程无解，即一次同余方程ax≡c (mod \;m)有解的充分必要条件是gcd(a,m)|c。
（1）充分性：
记d=gcd(a,m)，$a=da1，m=dm1，c=dc_1，
其中a1与m1互素，则存在x1和y1使得a1x1+m1y1=1。
令x=c1x1，y=c1y1，得a1x+m1y=c_1。
等式两边同乘d，得ax+my=c。
所以，ax≡c(mod \; m)，即x是方程的解。
（2）必要性：
设x是方程的解，则存在y使得ax+my=c。
则由性质：如果a|b且a|c，则对任意的整数x,y，有a|xb+yc得，有d|c.
设x0是方程的解，不难验证所有与x0模m同余的数都是方程的解，从而方程的解可以写成x≡x_0(mod \; m)。
于是，只需对模m$的每一个等价类取一个代表，验证是否使方程成立，就能找到方程的所有的解。
定理二：设m>0，d=\gcd(a,m)且d|c，证明：一次同余方程ax≡c(mod \; m)在模m下有d个解。
证明如下：
设$a=da1，m=dm1，其中设a1，m1互素。
根据定理，存在x0，使ax0≡c(mod\; m)，又设x是方程的解，即ax≡c(mod \; m)。
于是，a(x-x0)≡0(mod \; m)，它等价于a1(x-x0 )≡0(mod \; m1 )，
而a1与m1互素，故有x-x0≡0(mod \;m1 )。
因此，方程在模m下恰好有d个解x≡x0 + km1 (mod \; m_1),\quad k=0,1,…,d-1$。
五指山
Description
我们假设佛祖的手掌是一个圆圈（所以任凭大圣一个筋斗云十万八千里也是飞不出其手掌心），圆圈的长为n，逆时针记为：0,1,2,…,n-1，而大圣每次飞的距离为d.现在大圣所在的位置记为x,而大圣想去的地方在y。现在要你告诉大圣至少要多少筋斗云才能到达目的地。
Input
有多组测试数据。 第一行是一个正整数T，表示测试数据的组数。
每组测试数据包括一行，四个非负整数，
n(2x(0\leq x注意孙悟空的筋斗云只沿着逆时针方向翻。
Output
对于每组测试数据，输出一行，给出大圣最少要翻多少个筋斗云才能到达目的地。
如果无论翻多少个筋斗云也不能到达，输出"Impossible"。
Analysis
仍是同余方程问题，与上一题（青蛙的约会）思路一致，不再赘述，代码如下。
Code
#include <iostream>
#include <algorithm>
#define endl "\n"
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y) {
if(b 0) {
x = 1;
y = 0;
return a;
}
LL _x, _y;
LL d = exgcd(b, a % b, _x, _y);
x = _y;
y = _x - a / b * _y;
return d;
}
int main() {
int T;
cin >> T;
while(T --) {
LL n, d, x, y;
cin >> n >> d >> x >> y;
LL b = ((y - x) % n + n) % n;
LL D = exgcd(d, n, x, y);
LL t = n / D;
if(b % D)
puts("Impossible");
else
cout << (x * (b / D) % t + t) % t << endl;
}
return 0;
}
Fight 2018
Description
求2018^{n}的因子和模499的值，其中1 \leq n \leq 1e20。
Analysis
C++的\text{__int128}的读入
2018 = 2^{1} * 1009^{1}，2018^{n} = 2^{n} * 1009^{n}，
那么2018^{n}的因子和s= (2^0 + 2^1 + … 2^n) * (1009^0 + 1009^1 + … 1009^n)
\qquad \qquad \qquad \qquad = \frac{2^{n+1}-1}{2-1} * \frac{1009^{n+1}-1}{1009-1}
Code
#include <iostream>
#include <algorithm>
#define endl "\n"
using namespace std;
typedef __int128 LLL;
const int MOD = 499;
LLL quick_pow(LLL p, LLL k, LLL mod)
{
LLL res = 1;
while(k)
{
if(k & 1)
res = res * p % mod;
p = p * p % mod;
k >>= 1;
}
return res;
}
LLL read()
{
LLL n = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
n = n * 10 + c - '0';
c = getchar();
}
return n * f;
}
int main()
{
LLL n;
while(n = read(), n)
{
LLL a = (quick_pow(2, n + 1, MOD) - 1) % MOD ;
LLL b = (quick_pow(1009, n + 1, MOD) - 1) % MOD;
LLL c = quick_pow(1009 - 1, MOD - 2, MOD);
int res = a * b % MOD * c % MOD;
cout << res << endl;
}
return 0;
}
