欧几里得算法_给定 n,求 1 ≤ x <n中有多少个 x 与n 互质。如n=12,比12小的并与12互素的数有1-CSDN博客

博客介绍了求最大公约数的更相减损术、Stein算法和欧几里得算法，阐述了欧几里得算法的理论基础——带余除法定理及其在多项式、复数领域的泛化，还介绍了拓展欧几里得算法，并给出多个OJ实战题目及分析。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

二，欧几里得算法的理论基础——带余除法定理

UVALive 7045 Last Defence

（2）欧几里得算法——最大公约数

CSU 2038 N个数求和

CSU 1209 Three Jugs

CSU 1274 Balls and Boxes

CSU 1871 简单的数论

HDU 1222 Wolf and Rabbit（加法生成元）

力扣 2607. 使子数组元素和相等（加法生成元）

力扣 1819. 序列中不同最大公约数的数目

力扣 1979. 找出数组的最大公约数

力扣 2001. 可互换矩形的组数

力扣 2197. 替换数组中的非互质数

力扣 2280. 表示一个折线图的最少线段数

力扣 2344. 使数组可以被整除的最少删除次数

力扣 2436. 使子数组最大公约数大于一的最小分割数

力扣 2447. 最大公因数等于 K 的子数组数目

力扣 2654. 使数组所有元素变成 1 的最少操作次数

HDU 1019 Least Common Multiple

HDU 5584 LCM Walk

CSU 1124 最终时刻

POJ 3101 Astronomy

力扣 2470. 最小公倍数为 K 的子数组数目

力扣 878. 第 N 个神奇数字

力扣 1201. 丑数 III

力扣 2513. 最小化两个数组中的最大值

力扣 2652. 倍数求和

（4）拓展欧几里得算法

CSU 1252 求逆元

HDU 1356 The Balance（拓展欧几里得算法的解空间结构）

SCU 1269、UVA 10090 Marbles

POJ 2115 C Looooops

POJ 1061 青蛙的约会

一，最大公约数

最大公约数的三个类似算法：

（1）更相减损术

《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，原文是：
可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

断章取义（忽略半之）：如果a>b那么gcd(a,b)=gcd(a-b,b) ，一直减下去，就能求出最大公约数。

（2）Stein算法

这个算法包含可半者半之，即gcd(2a,2b)=gcd(a,b)

（3）欧几里得算法

欧几里得算法又称辗转相除法。

long long gcd(long long a, long long b)
{
	return b ? gcd(b, a%b) : a;
}

二，欧几里得算法的理论基础——带余除法定理

欧几里得算法主要依赖带余除法定理：

设a , b是两个整数,且b != 0,则存在唯一的整数 q , r (0 <= r < |b|),使得 a = q * b + r

如果将带余除法加以泛化，欧几里得算法就能用在其他领域。

三，欧几里得算法的泛化

欧几里得算法的适用领域是欧几里得整环数学与泛型编程（4）环

（1）多项式

多项式带余除法：对一元多项式环P[x]中任意两个多项式f(x)和g(x)≠0，一定存在P[x]中的多项式q(x)，r(x)，使f(x)=g(x)q(x)+r(x)，式中r(x)=0或r(x)的次数小于g(x)的次数，并且这样的q(x)与r(x)是惟一确定的。当r(x)=0时，称g(x)除尽f(x)

求多项式的最大公约式：

（2）复数

算术基本定理：每个整数都有唯一的一种素因子分解形式。

复数不满足算术基本定理，比如：

所以，复数没有对应的带余除法定理。

高斯复数：实部与虚部均为整数的那种复数。

高斯复数有带余除法，所以高斯复数可以用欧几里得算法求最大公约数：

四，拓展欧几里得算法

裴蜀定理：若a,b是整数，且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

在欧几里得算法求d的过程中，x和y的值实际上已经差不多求出来了，这就是拓展欧几里得算法。

//求任意x,y，ax-by=gcd(a,b)
long long gcd(long long a, long long b, long long &x, long long &y)
{
	if (b == 0) {
		x = 1, y = 0;
		return a;
	}
	auto g = gcd(b, a%b, x, y);
	auto t = -a / b * y - x;
	x = -y, y = t;
	return g;
}

五，OJ实战

（1）更相减损术

UVALive 7045 Last Defence

题目：

代码：

#include<iostream>
using namespace std;

long long f(long long a, long long b)
{
	if (b == 0)return (a>0)+1;
	if (a < b)return f(b, a);
	return f(a%b, b) + (a - 1) / b;
}

int main()
{	
	int t;
	cin >> t;
	long long a, b;
	for (int cas = 1; cas <= t;cas++)
	{
		cin >> a >> b;
		cout << "Case #" << cas << ": " << f(a, b) << endl;
	}
	return 0;
}

（2）欧几里得算法——最大公约数

CSU 2038 N个数求和

题目：

Description

本题的要求很简单，就是求N个数字的和。麻烦的是，这些数字是以有理数“分子/分母”的形式给出的，你输出的和也必须是有理数的形式。

Input

输入第一行给出一个正整数T，代表数据组数。每组数据第一行给出一个整数N（<=100）。随后一行按格式“a1/b1 a2/b2 ...”给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符号一定出现在分子前面。

Output

输出上述数字和的最简形式 —— 即将结果写成“整数部分分数部分”，其中分数部分写成“分子/分母”，要求分子小于分母，且它们没有公因子。如果结果的整数部分为0，则只输出分数部分。

Sample Input

1
5
2/5 4/15 1/30 -2/60 8/3

Sample Output

3 1/3

Hint

当计算结果为正数时，应当是“整数部分+分数部分”
当计算结果为负数时，应当是“整数部分-分数部分”

代码：

#include<iostream>
using namespace std;
 
long long gcd(long long a, long long b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}
 
int main()
{
	int t, n;
	char c;
	cin >> t;
	while (t--)
	{
		long long a, b, ansa = 0, ansb = 1;
		cin >> n;
		while (n--)
		{
			cin >> a >> c >> b;
			long long g = gcd(ansb, b);
			long long ta = b / g * ansa + ansb / g * a, tb = ansb / g * b;
			ansa = ta / gcd(ta, tb), ansb = tb / gcd(ta, tb);
		}
		if (ansa%ansb == 0)cout << ansa / ansb;
		else
		{
			if (ansb < 0)ansa *= -1, ansb *= -1;
			if (ansa < 0)
			{
				cout << '-';
				ansa *= -1;
			}
			if (ansa >= ansb)cout << ansa / ansb << " ";
			cout << ansa % ansb << '/' << ansb;
		}
		cout << endl;
	}
	return 0;
}

CSU 1209 Three Jugs

题目：

Description

    We have three jugs A, B, C without any calibration, and an infinite supply of water. There are three types of actions that you can use:
     (1) Fill a jug.
     (2) Empty a jug.
     (3) Pour from one jug to another.
    Pouring from one jug to another stops when the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons, B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.
    Now you need to calculate the minimum accurate gallons of water we can get by using the three jugs.

Input

There is an integer T (1 <= T <= 200) in the first line, means there are T test cases in total.
For each test case, there are three integers a, b, c (1 <= a, b, c <= 10^18) in a line, indicate the capacity (unit: gallon) of the three jugs.

Output

For each test case, you should print one integer in a line, indicates the minimum accurate gallons of water we can get by using the three jugs.

Sample Input

2
3 6 9
6 10 15

Sample Output

3
1

首先要理解题目，其实就是直接求a,b,c的最大公约数就可以了。

#include<iostream>
using namespace std;

long long gcd(long long a, long long b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}

int main()
{
	int n;
	cin >> n;
	long long a, b, c;
	while (n--)
	{
		cin >> a >> b >> c;
		b = gcd(a, b);
		cout << gcd(b,c) << endl;
	}
	return 0;
}

CSU 1274 Balls and Boxes

题目：

Description

在初始时刻M个盒子中各有若干个球，每一次操作可以任选N (N < M)个盒子，然后在每个选择的盒子中各加1个球。

Input

输入的第一行包含一个整数T (1 <= T <= 200)，表示接下来一共有T组测试数据。

对于每组测试数据，第一行包含两个整数M, N (1 <= N < M <= 104)。接下来一行包含M个不大于105的非负整数，分别描述了初始时刻M个盒子中球的数量。

Output

用一行输出一个整数，表示最少需要操作多少次才可能让各个盒子中球的数量相等。

如果无论怎样操作都不能达到这个目的，则用一行输出“-1”（不包含引号）。

Sample Input

Sample Output

0
3
-1

这个题目包含的数学知识还挺多的，注意溢出的问题。

#include<iostream>
#define ll long long
using namespace std;
 
ll gcd(ll a, ll b)
{
	if (b)return gcd(b, a%b);
	return a;
}
 
int main()
{
	ll T, m, n, num[10001];
	cin >> T;
	while (T--)
	{
		cin >> m >> n;
		ll max = 0, min = 100000, sum = 0;
		for (int i = 1; i <= m; i++)
		{
			cin >> num[i];
			if (max < num[i])max = num[i];
			if (min > num[i])min = num[i];
			sum += num[i];
		}
		ll g = gcd(m, n);
		if (sum%g)cout << -1 << endl;
		else if (max == min)cout << 0 << endl;
		else
		{
			ll ans = (max*m - sum - 1) / n + 1;
			while ((ans*n + sum) % m)ans++;
			while (ans + min < (ans*n + sum) / m)ans += m / g;
			cout << ans << endl;
		}
	}
	return 0;
}

CSU 1871 简单的数论

题目：

Description

擅长数学的小A君不满足于简单的求解最大公约数和最小公倍数的问题了，他研究出了一个新的题型准备去考考小B，小A给小B 4个正整数a，b，c，d，他问小B能否找到一个数x，使得a和x的最大公约数为b，c和x的最小公倍数为d。如果有多个这样的x，将所有的x按由小到大的顺序列出来，如果找不到任何一个这样的x，那么就输出-1。

Input

第一行给定一个正整数T，表示有T组数据（T<=100）接下来T行每行输入4个正整数a，b，c，d （这四个数都小于2^31）

Output

对于每组数据按照从小到大的顺序输出所有的x的值，如果一个x都找不到则输出-1。

Sample Input

1
6 3 5 15

Sample Output

3 15

代码：

#include<iostream>
using namespace std;
 
int gcd(int a, int b)
{
	if (b)return gcd(b, a%b);
	return a;
}
 
void f2(int a, int b, int c, int d)
{
	if (a%b!=0 || d%c!=0 || d%b!=0)
	{
		cout << -1;
		return;
	}
	int g = gcd(a / b, d / c), p = d / b;
	if (gcd(g,p)>1)
	{
		cout << -1;
		return;
	}
	a /= b, d /= c;
	while (gcd(a, p) > 1)p /= gcd(a, p);
	while (gcd(d, p) > 1)b *= gcd(d, p), p /= gcd(d, p);
	int i;
	for (i = 1; i*i <= p; i++)if (p%i == 0)cout << i*b << " ";
	for (; i > 0; i--)if (p%i == 0 && i*i<p)cout << p / i*b << " ";
}
 
int main()
{
	int t, a, b, c, d;
	cin >> t;
	while (t--)
	{
		cin >> a >> b >> c >> d;
		f2(a, b, c, d);
		cout << endl;
	}
	return 0;
}

HDU 1222 Wolf and Rabbit（加法生成元）

题目：

Description

There is a hill with n holes around. The holes are signed from 0 to n-1.

A rabbit must hide in one of the holes. A wolf searches the rabbit in anticlockwise order. The first hole he get into is the one signed with 0. Then he will get into the hole every m holes. For example, m=2 and n=6, the wolf will get into the holes which are signed 0,2,4,0. If the rabbit hides in the hole which signed 1,3 or 5, she will survive. So we call these holes the safe holes.

Input

The input starts with a positive integer P which indicates the number of test cases. Then on the following P lines,each line consists 2 positive integer m and n(0<m,n<2147483648).

Output

For each input m n, if safe holes exist, you should output "YES", else output "NO" in a single line.

Sample Input

2
1 2
2 2

Sample Output

NO
YES

一个非常简单的数论问题，判断m是否是mod n的加法生成元。

只要看m和n是否互质即可。

代码：

#include<iostream>
using namespace std;

int gcd(int a, int b)
{
	if (b)return gcd(b, a%b);
	return a;
}

int main()
{
	int n, a, b;
	cin >> n;
	while (n--)
	{
		cin >> a >> b;
		if (gcd(a, b) == 1)cout << "NO\n";
		else cout << "YES\n";
	}
	return 0;
}

力扣 2607. 使子数组元素和相等（加法生成元）

给你一个下标从 0 开始的整数数组 arr 和一个整数 k 。数组 arr 是一个循环数组。换句话说，数组中的最后一个元素的下一个元素是数组中的第一个元素，数组中第一个元素的前一个元素是数组中的最后一个元素。

你可以执行下述运算任意次：

选中 arr 中任意一个元素，并使其值加上 1 或减去 1 。

执行运算使每个长度为 k 的 子数组 的元素总和都相等，返回所需要的最少运算次数。

子数组 是数组的一个连续部分。

示例 1：

输入：arr = [1,4,1,3], k = 2
输出：1
解释：在下标为 1 的元素那里执行一次运算，使其等于 3 。
执行运算后，数组变为 [1,3,1,3] 。
- 0 处起始的子数组为 [1, 3] ，元素总和为 4 
- 1 处起始的子数组为 [3, 1] ，元素总和为 4 
- 2 处起始的子数组为 [1, 3] ，元素总和为 4 
- 3 处起始的子数组为 [3, 1] ，元素总和为 4

示例 2：

输入：arr = [2,5,5,7], k = 3
输出：5
解释：在下标为 0 的元素那里执行三次运算，使其等于 5 。在下标为 3 的元素那里执行两次运算，使其等于 5 。
执行运算后，数组变为 [5,5,5,5] 。
- 0 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 1 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 2 处起始的子数组为 [5, 5, 5] ，元素总和为 15
- 3 处起始的子数组为 [5, 5, 5] ，元素总和为 15

提示：

1 <= k <= arr.length <= 105
1 <= arr[i] <= 109

class Solution {
public:
	long long makeSubKSumEqual(vector<int>& arr) {
		sort(arr.begin(), arr.end());
		int mid = arr[(arr.size() - 1) / 2] + arr[arr.size() / 2];
		long long ans = 0;
		for (auto x : arr)ans += abs(x + x - mid);
		return ans / 2;
	}
	long long makeSubKSumEqual(vector<int>& arr, int k) {
		int g = Gcd(arr.size(), k);
		long long ans = 0;
		for (int i = 0; i < g; i++) {
			vector<int>v;
			for (int j = i; j < arr.size(); j += g)v.push_back(arr[j]);
			ans += makeSubKSumEqual(v);
		}
		return ans;
	}
};

CSU 1756 Prime

题目：

Description
如果a,b的最大公约数是1，说明a,b是一对互素的数，给定你n个数字，希望你找出互素的数的对数

Input
第一行输入一个正整数T，表示数据组数

每组数据第一行输入一个正整数n，表示数字的个数(n<=10000)

接下来一行输入n个正整数，每个数字大小不超过1000。

Output
输出互素的数的对数

Sample Input
1
4
10 9 6 35
Sample Output
3
这个题目的输入量是10000，如果用平方的方法的话应该会超时。
虽然这么想着，不过我还是神不知鬼不觉的把代码写出来提交了。

代码：

#include<iostream>
#include<string.h>
using namespace std;

bool f(int a, int b)
{
	if (a == 1 || b == 1)return true;
	if (a == 0 || b == 0)return false;
	if (a > b)return f(a - b, b);
	return f(a, b - a);
}

int list[10000];

int main()
{
	int cas;
	cin >> cas;
	int sum;
	while (cas--)
	{
		int n;
		cin >> n;
		memset(list, 0, sizeof(list));
		for (int i = 0; i < n; i++)cin >> list[i];
		sum = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				if (f(list[i], list[j]))sum++;
			}
		}
		cout << sum << endl;
	}
	return 0;
}

然后果然超时了，3秒果然不够用。

然后只能用计重的方法了，因为每个数都不超过1000。

我想到的计重的方法有2种，第一种是，直接记录从1到1000每个数出现的次数，用1个长1000的数组就可以了。

不过这种方法我并没有实现，因为我觉得方法二更快。

方法二：把10000个数排序，然后计重的同时我们会得到一个有多少个数，

比如如果有100个数的话，后面的步骤就是100个数两两比较，而不是1000个，这样就比较快。

代码：

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

bool f(int a, int b)
{
	if (a == 1 || b == 1)return true;
	if (a == 0 || b == 0)return false;
	if (a > b)return f(a - b, b);
	return f(a, b - a);
}

int list[10000];
struct node
{
	int a;
	int num;
};

int main()
{
	int cas;
	cin >> cas;
	int sum;
	while (cas--)
	{
		int n;
		cin >> n;
		memset(list, 0, sizeof(list));
		for (int i = 0; i < n; i++)cin >> list[i];
		sort(list, list + n);
		node nod[1001];
		int i = 0, j = 0;
		nod[0].a = -1;
		while (i < n)
		{
			if (list[i] == nod[j].a)nod[j].num++;
			else
			{
				j++;
				nod[j].a = list[i];
				nod[j].num = 1;
			}
			i++;
		}
		sum = 0;
		for (int i = 1; i <= j; i++)
		{
			for (int k = i+1; k <= j; k++)
			{
				if (f(nod[i].a, nod[k].a))sum += nod[i].num*nod[k].num;
			}
		}
		if (nod[1].a == 1)sum += nod[1].num*(nod[1].num - 1) / 2;
		cout << sum << endl;
	}
	return 0;
}

这个代码确实过了，然而并不快。

我是1172ms，还有2个人过了，一个是604ms，另外一居然是180ms。

我想了一下，这个方法也有它的缺点，缺点就是排序本身花了大量时间。

总的来说2种计重的方法谁好谁坏是说不清楚的，要看输入的数据的特性。如果输入了10000个数，从1到1000都有，那我这个方法效率就不高了。

还有1个需要注意的地方，如果有1的话，1和1也是互素的，所以我最后加了一句

f (nod[1].a == 1)sum += nod[1].num*(nod[1].num - 1) / 2;

力扣 858. 镜面反射

有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 0， 1，以及 2。

正方形房间的墙壁长度为 p，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 0 的距离为 q 。

返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。

示例 1：

输入：p = 2, q = 1
输出：2
解释：这条光线在第一次被反射回左边的墙时就遇到了接收器 2 。

示例 2：

输入：p = 3, q = 1
输入：1

提示：

1 <= q <= p <= 1000

思路：

直接把正方形做翻转平铺，铺满整个平面。

class Solution {
public:
	int mirrorReflection(int p, int q) {
		int x = p / Gcd(p, q);
		int y = q / Gcd(p, q);
		if ((x - y) % 2 == 0)return 1;
		return y % 2 * 2;
	}
};

力扣 914. 卡牌分组

给定一副牌，每张牌上都写着一个整数。

此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

每组都有 X 张牌。
组内所有的牌上都写着相同的整数。

仅当你可选的 X >= 2 时返回 true。

示例 1：

输入：deck = [1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]

示例 2：

输入：deck = [1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。

提示：

1 <= deck.length <= 104
0 <= deck[i] < 104

class Solution {
public:
    bool hasGroupsSizeX(vector<int>& deck) {
        auto v=Fshr(deck);
        int ans=0;
        for(auto vi:v)ans=Gcd(vi.second,ans);
        return ans>1;
    }
};

力扣 1447. 最简分数

给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的最简分数。分数可以以任意顺序返回。

示例 1：

输入：n = 2
输出：["1/2"]
解释："1/2" 是唯一一个分母小于等于 2 的最简分数。

示例 2：

输入：n = 3
输出：["1/2","1/3","2/3"]

示例 3：

输入：n = 4
输出：["1/2","1/3","1/4","2/3","3/4"]
解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。

示例 4：

输入：n = 1
输出：[]

提示：

1 <= n <= 100

class Solution {
public:
	vector<string> simplifiedFractions(int n) {
		vector<string>ans;
		for (int i = 2; i <= n; i++) {
			for (int j = 1; j < i; j++) {
				if (Gcd(i, j) == 1)ans.push_back(to_string(j) + "/" + to_string(i));
			}
		}
		return ans;
	}
};

力扣 1819. 序列中不同最大公约数的数目

给你一个由正整数组成的数组 nums 。

数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。

例如，序列 [4,6,16] 的最大公约数是 2 。

数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。

例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

计算并返回 nums 的所有非空子序列中不同最大公约数的数目。

示例 1：

输入：nums = [6,10,3]
输出：5
解释：上图显示了所有的非空子序列与各自的最大公约数。
不同的最大公约数为 6 、10 、3 、2 和 1 。

示例 2：

输入：nums = [5,15,40,5,6]
输出：7

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 2 * 105

class Solution {
public:
	int countDifferentSubsequenceGCDs(vector<int>& nums) {
		int ans = 0, maxNum = 0;
		int m[200001];
        memset(m,0,sizeof(m));
		for (auto n : nums)m[n] = 1, maxNum = max(maxNum, n);
		for (int i = 1; i <= maxNum; i++) {
			int g = 0;
			for (int j = i; j <= maxNum; j += i) {
				if (m[j])g = Gcd(g, j);
				if (g == i)break;
			}
			ans += (g == i);
		}
		return ans;
	}
};

力扣 1979. 找出数组的最大公约数

给你一个整数数组 nums ，返回数组中最大数和最小数的 最大公约数 。

两个数的 最大公约数 是能够被两个数整除的最大正整数。

示例 1：

输入：nums = [2,5,6,9,10]
输出：2
解释：
nums 中最小的数是 2
nums 中最大的数是 10
2 和 10 的最大公约数是 2

示例 2：

输入：nums = [7,5,6,8,3]
输出：1
解释：
nums 中最小的数是 3
nums 中最大的数是 8
3 和 8 的最大公约数是 1

示例 3：

输入：nums = [3,3]
输出：3
解释：
nums 中最小的数是 3
nums 中最大的数是 3
3 和 3 的最大公约数是 3

提示：

2 <= nums.length <= 1000
1 <= nums[i] <= 1000

class Solution {
public:
	int findGCD(vector<int>& nums) {
		int a = INT_MAX, b = 0;
		for (auto x : nums)a = min(a, x), b = max(b, x);
		return Gcd(a, b);
	}
};

力扣 2001. 可互换矩形的组数

用一个下标从 0 开始的二维整数数组 rectangles 来表示 n 个矩形，其中 rectangles[i] = [widthi, heighti] 表示第 i 个矩形的宽度和高度。

如果两个矩形 i 和 j（i < j）的宽高比相同，则认为这两个矩形 可互换 。更规范的说法是，两个矩形满足 widthi/heighti == widthj/heightj（使用实数除法而非整数除法），则认为这两个矩形 可互换 。

计算并返回 rectangles 中有多少对 可互换 矩形。

示例 1：

输入：rectangles = [[4,8],[3,6],[10,20],[15,30]]
输出：6
解释：下面按下标（从 0 开始）列出可互换矩形的配对情况：
- 矩形 0 和矩形 1 ：4/8 == 3/6
- 矩形 0 和矩形 2 ：4/8 == 10/20
- 矩形 0 和矩形 3 ：4/8 == 15/30
- 矩形 1 和矩形 2 ：3/6 == 10/20
- 矩形 1 和矩形 3 ：3/6 == 15/30
- 矩形 2 和矩形 3 ：10/20 == 15/30

示例 2：

输入：rectangles = [[4,5],[7,8]]
输出：0
解释：不存在成对的可互换矩形。

提示：

n == rectangles.length
1 <= n <= 105
rectangles[i].length == 2
1 <= widthi, heighti <= 105

class Solution {
public:
	long long interchangeableRectangles(vector<vector<int>>& rectangles) {
		map<int, map<int, long long>>m;
		for (auto v : rectangles) {
			int g = Gcd(v[0], v[1]);
			m[v[0] / g][v[1] / g]++;
		}
		long long ans = 0;
		for (auto &mi : m) {
			for (auto pair : mi.second)ans += pair.second*(pair.second - 1) / 2;
		}
		return ans;
	}
};

力扣 2197. 替换数组中的非互质数

给你一个整数数组 nums 。请你对数组执行下述操作：

从 nums 中找出任意两个相邻的 非互质 数。
如果不存在这样的数，终止这一过程。
否则，删除这两个数，并替换为它们的 最小公倍数（Least Common Multiple，LCM）。
只要还能找出两个相邻的非互质数就继续重复这一过程。

返回修改后得到的最终数组。可以证明的是，以任意顺序替换相邻的非互质数都可以得到相同的结果。

生成的测试用例可以保证最终数组中的值 小于或者等于 108 。

两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的 最大公约数 。

示例 1 ：

输入：nums = [6,4,3,2,7,6,2]
输出：[12,7,6]
解释：
- (6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。
- (12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。
- (12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。
- (6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。
现在，nums 中不存在相邻的非互质数。
因此，修改后得到的最终数组是 [12,7,6] 。
注意，存在其他方法可以获得相同的最终数组。

示例 2 ：

输入：nums = [2,2,1,1,3,3,3]
输出：[2,1,1,3]
解释：
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。
- (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。
- (2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。
现在，nums 中不存在相邻的非互质数。 
因此，修改后得到的最终数组是 [2,1,1,3] 。 
注意，存在其他方法可以获得相同的最终数组。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 105
生成的测试用例可以保证最终数组中的值 小于或者等于 108 。

class Solution {
public:
	vector<int> replaceNonCoprimes(vector<int>& nums) {
		stack<int>ans;
		for (auto b : nums) {
			while (!ans.empty()) {
				int t = ans.top();
				auto g = Gcd(t, b);
				if (g == 1)break;
				b *= t / g;
				ans.pop();
			}
			ans.push(b);
		}
		return StackToVec(ans);
	}
};

力扣 2280. 表示一个折线图的最少线段数

给你一个二维整数数组 stockPrices ，其中 stockPrices[i] = [dayi, pricei] 表示股票在 dayi 的价格为 pricei 。折线图 是一个二维平面上的若干个点组成的图，横坐标表示日期，纵坐标表示价格，折线图由相邻的点连接而成。比方说下图是一个例子：

请你返回要表示一个折线图所需要的 最少线段数 。

示例 1：

输入：stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
输出：3
解释：
上图为输入对应的图，横坐标表示日期，纵坐标表示价格。
以下 3 个线段可以表示折线图：
- 线段 1 （红色）从 (1,7) 到 (4,4) ，经过 (1,7) ，(2,6) ，(3,5) 和 (4,4) 。
- 线段 2 （蓝色）从 (4,4) 到 (5,4) 。
- 线段 3 （绿色）从 (5,4) 到 (8,1) ，经过 (5,4) ，(6,3) ，(7,2) 和 (8,1) 。
可以证明，无法用少于 3 条线段表示这个折线图。

示例 2：

输入：stockPrices = [[3,4],[1,2],[7,8],[2,3]]
输出：1
解释：
如上图所示，折线图可以用一条线段表示。

提示：

1 <= stockPrices.length <= 105
stockPrices[i].length == 2
1 <= dayi, pricei <= 109
所有 dayi 互不相同 。

class Solution {
public:
	int minimumLines(vector<vector<int>>& stockPrices) {
		if (stockPrices.size() < 2)return 0;
		sort(stockPrices.begin(), stockPrices.end());
		for (int i = stockPrices.size() - 1; i > 0; i--) {
			stockPrices[i][0] -= stockPrices[i - 1][0];
			stockPrices[i][1] -= stockPrices[i - 1][1];
		}
		int ans = 1;
		for (int i = 1; i < stockPrices.size(); i++) {
			int g = Gcd(stockPrices[i][0], stockPrices[i][1]);
			stockPrices[i][0] /= g, stockPrices[i][1] /= g;
			if (i > 1 && (stockPrices[i][0] != stockPrices[i - 1][0] || stockPrices[i][1] != stockPrices[i - 1][1]))ans++;
		}
		return ans;
	}
};

力扣 2344. 使数组可以被整除的最少删除次数

给你两个正整数数组 nums 和 numsDivide 。你可以从 nums 中删除任意数目的元素。

请你返回使 nums 中最小元素可以整除 numsDivide 中所有元素的最少删除次数。如果无法得到这样的元素，返回 -1 。

如果 y % x == 0 ，那么我们说整数 x 整除 y 。

示例 1：

输入：nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
输出：2
解释：
[2,3,2,4,3] 中最小元素是 2 ，它无法整除 numsDivide 中所有元素。
我们从 nums 中删除 2 个大小为 2 的元素，得到 nums = [3,4,3] 。
[3,4,3] 中最小元素为 3 ，它可以整除 numsDivide 中所有元素。
可以证明 2 是最少删除次数。

示例 2：

输入：nums = [4,3,6], numsDivide = [8,2,6,10]
输出：-1
解释：
我们想 nums 中的最小元素可以整除 numsDivide 中的所有元素。
没有任何办法可以达到这一目的。

提示：

1 <= nums.length, numsDivide.length <= 105
1 <= nums[i], numsDivide[i] <= 109

class Solution {
public:
	int minOperations(vector<int>& nums, vector<int>& numsDivide) {
		long long x = 0;
		for (auto d : numsDivide)x = Gcd(x, d);
		int m = INT_MAX;
		for (auto n : nums)if (x%n == 0)m = min(m, n);
		if (m == INT_MAX)return -1;
		int ans = 0;
		for (auto n : nums)if (n < m)ans++;
		return ans;
	}
};

力扣 2436. 使子数组最大公约数大于一的最小分割数

给定一个由正整数组成的数组 nums。

将数组拆分为 一个或多个 不相连的子数组，如下所示:

数组中的每个元素都 只属于一个 子数组，并且
每个子数组元素的 最大公约数 严格大于 1。

返回拆分后可获得的子数组的最小数目。

注意:

子数组的 最大公约数 是能将子数组中所有元素整除的最大正整数。
子数组 是数组的连续部分。

示例 1:

输入: nums = [12,6,3,14,8]
输出: 2
解释: 我们可以把数组分成子数组:[12,6,3] 和 [14,8]。
- 12、6、3 的最大公约数是 3，严格大于 1。
- 14 和 8 的最大公约数是 2，严格来说大于 1。
可以看出，如果不拆分数组将使最大公约数 = 1。

示例 2:

输入: nums = [4,12,6,14]
输出: 1
解释: 我们可以将数组拆分为一个子数组，即整个数组。

提示:

1 <= nums.length <= 2000
2 <= nums[i] <= 109

class Solution {
public:
	int minimumSplits(vector<int>& nums) {
		int ans = 0, x = 0;
		for (auto num:nums)
		{
			x = Gcd(x, num);
			if (x == 1) {
				ans++;
				x = num;
			}
		}
		return ans+1;
	}
};

力扣 2447. 最大公因数等于 K 的子数组数目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。

子数组是数组中一个连续的非空序列。

数组的最大公因数是能整除数组中所有元素的最大整数。

示例 1：

输入：nums = [9,3,1,2,6,3], k = 3
输出：4

示例 2：

输入：nums = [4], k = 7
输出：0
解释：不存在以 7 作为最大公因数的子数组。

提示：

1 <= nums.length <= 1000
1 <= nums[i], k <= 109

class Solution {
public:
    int subarrayGCD(vector<int>& nums, int k) {
        int s=0;
        for(int i=0;i<nums.size();i++){
            int x=nums[i];
            s+=(x==k);
            for(int j=i+1;j<nums.size();j++){
                x=gcd(x,nums[j]);
                s+=(x==k);
            }
        }
        return s;
    }
};

力扣 2654. 使数组所有元素变成 1 的最少操作次数

给你一个下标从 0 开始的正整数数组 nums 。你可以对数组执行以下操作任意次：

选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。

请你返回使数组 nums 中所有元素都等于 1 的最少操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。

示例 1：

输入：nums = [2,6,3,4]
输出：4
解释：我们可以执行以下操作：
- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。

示例 2：

输入：nums = [2,10,6,14]
输出：-1
解释：无法将所有元素都变成 1 。

提示：

2 <= nums.length <= 50
1 <= nums[i] <= 106

class Solution {
public:
	int minOperations(vector<int>& nums) {
		auto v = nums;
		int a = 0, b = 0;
		for (auto x : v)if (x == 1)a++; else b++;
		if (a)return b;
		for (int k = 0; k < nums.size(); k++) {
			for (int i = 0; i < v.size(); i++) {
				v[i] = Gcd(v[i], nums[k + i]);
				if (v[i] == 1)return k + nums.size() - 1;
			}
			v.erase(v.end() - 1);
		}
		return -1;
	}
};

力扣 2748. 美丽下标对的数目

给你一个下标从 0 开始的整数数组 nums 。如果下标对 i、j 满足 0 ≤ i < j < nums.length ，如果 nums[i] 的 第一个数字 和 nums[j] 的 最后一个数字 互质，则认为 nums[i] 和 nums[j] 是一组 美丽下标对 。

返回 nums 中 美丽下标对 的总数目。

对于两个整数 x 和 y ，如果不存在大于 1 的整数可以整除它们，则认为 x 和 y 互质。换而言之，如果 gcd(x, y) == 1 ，则认为 x 和 y 互质，其中 gcd(x, y) 是 x 和 k 最大公因数 。

示例 1：

输入：nums = [2,5,1,4]
输出：5
解释：nums 中共有 5 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 2 ，nums[1] 的最后一个数字是 5 。2 和 5 互质，因此 gcd(2,5) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 2 ，nums[1] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(2,1) == 1 。
i = 1 和 j = 2 ：nums[0] 的第一个数字是 5 ，nums[1] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(5,1) == 1 。
i = 1 和 j = 3 ：nums[0] 的第一个数字是 5 ，nums[1] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(5,4) == 1 。
i = 2 和 j = 3 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(1,4) == 1 。
因此，返回 5 。

示例 2：

输入：nums = [11,21,12]
输出：2
解释：共有 2 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 1 。gcd(1,1) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 2 。gcd(1,2) == 1 。
因此，返回 2 。

提示：

2 <= nums.length <= 100
1 <= nums[i] <= 9999
nums[i] % 10 != 0

class Solution {
public:
	int countBeautifulPairs(vector<int>& nums) {
		vector<int>v1, v2;
		for (auto x : nums) {
			v2.push_back(x % 10);
			while (x >= 10)x /= 10;
			v1.push_back(x);
		}
		int ans = 0;
		for (int i = 0; i < nums.size(); i++) {
			for (int j = i + 1; j < nums.size(); j++) {
				if (Gcd(v1[i], v2[j]) == 1)ans++;
			}
		}
		return ans;
	}
};

力扣 2807. 在链表中插入最大公约数

给你一个链表的头 head ，每个结点包含一个整数值。

在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的 最大公约数 。

请你返回插入之后的链表。

两个数的 最大公约数 是可以被两个数字整除的最大正整数。

示例 1：

输入：head = [18,6,10,3]
输出：[18,6,6,2,10,1,3]
解释：第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。
- 18 和 6 的最大公约数为 6 ，插入第一和第二个结点之间。
- 6 和 10 的最大公约数为 2 ，插入第二和第三个结点之间。
- 10 和 3 的最大公约数为 1 ，插入第三和第四个结点之间。
所有相邻结点之间都插入完毕，返回链表。

示例 2：

输入：head = [7]
输出：[7]
解释：第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。
没有相邻结点，所以返回初始链表。

提示：

链表中结点数目在 [1, 5000] 之间。
1 <= Node.val <= 1000

class Solution {
public:
	ListNode* insertGreatestCommonDivisors(ListNode* head) {
		ListNode* p = head, *p2 = p->next;
		while (p2) {
			ListNode* pnew = new ListNode();
			pnew->val= Gcd(p->val, p2->val);
			pnew->next = p2, p->next = pnew;
			p = p2, p2 = p2->next;
		}
		return head;
	}
};

力扣 2941. 子数组的最大 GCD-Sum

给定一个整数数组 nums 和一个整数 k.

数组 a 的 gcd-sum 计算方法如下：

设 s 为 a 的所有元素的和。
设 g 为 a 的所有元素的 最大公约数。
a 的 gcd-sum 等于 s * g.

返回 nums 的至少包含 k 个元素的子数组的 最大 gcd-sum。

示例 1：

输入：nums = [2,1,4,4,4,2], k = 2
输出：48
解释：我们选择子数组 [4,4,4]，该数组的 gcd-sum 为 4 * (4 + 4 + 4) = 48。
可以证明我们无法选择任何其他 gcd-sum 大于 48 的子数组。

示例 2：

输入：nums = [7,3,9,4], k = 1
输出：81
解释：我们选择子数组 [9]，该数组的 gcd-sum 为 9 * 9 = 81。
可以证明我们无法选择任何其他 gcd-sum 大于 81 的子数组。

提示：

n == nums.length
1 <= n <= 105
1 <= nums[i] <= 106
1 <= k <= n

思路：

考虑以num[i]为结尾的子数组的gcd值，实际上可能的值非常少，于是可以依次递推，即数列DP

struct Node{
    int num;
    int g;
    long long s;
};
class Solution {
public:
    long long maxGcdSum(vector<int>& nums, int k) {
        vector<vector<Node>>v(nums.size());
        v[0]=vector<Node>{Node{1,nums[0],nums[0]}};
        long long ans=0;
        if(v[0][0].num>=k)ans=v[0][0].g*v[0][0].s;
        for(int i=1;i<v.size();i++){
            v[i].push_back(Node{1,nums[i],nums[i]});
            if(v[i][0].num>=k)ans=max(ans,v[i][0].g*v[i][0].s);
            for(auto &nod:v[i-1]){
                int num=nod.num+1;
                int g=Gcd(nod.g,nums[i]);
                long long s=nod.s+nums[i];
                if(num>=k)ans=max(ans,g*s);
                if(v[i].rbegin()->g==g){
                    v[i].rbegin()->num=num,v[i].rbegin()->s=s;
                }else{
                    v[i].push_back(Node{num,g,s});
                }
            }
        }
        return ans;
    }
};

（3）欧几里得算法——最小公倍数

HDU 1108 最小公倍数

题目：

Description

给定两个正整数，计算这两个数的最小公倍数。

Input

输入包含多组测试数据，每组只有一行，包括两个不大于1000的正整数.

Output

对于每个测试用例，给出这两个数的最小公倍数，每个实例输出一行。

Sample Input

10 14

Sample Output

代码：

#include<iostream>
using namespace std;

int gcd(int a, int b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}

int main()
{
	int a, b;
	while (cin >> a >> b)cout << a*b / gcd(a, b) << endl;
	return 0;
}

HDU 1019 Least Common Multiple

题目：

Description

The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105.

Input

Input will consist of multiple problem instances. The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number of integers in the set and n1 ... nm are the integers. All integers will be positive and lie within the range of a 32-bit integer.

Output

For each problem instance, output a single line containing the corresponding LCM. All results will lie in the range of a 32-bit integer.

Sample Input

2
3 5 7 15
6 4 10296 936 1287 792 1

Sample Output

105
10296

利用gcd求lcm即可

因为所给的数都是int，所以我都用long long来输入、计算，就没有越界的问题了。

代码：

#include<iostream>
using namespace std;

long long gcd(long long a, long long b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}

long long lcm(long long a, long long b)
{
	return a*b / gcd(a, b);
}

int main()
{	
	int t, n;
	long long r, a;
	cin >> t;
	while (t--)
	{
		cin >> n;
		r = 1;
		while (n--)
		{
			cin >> a;
			r = lcm(r, a);
		}
		cout << r << endl;
	}
	return 0;
}

HDU 5584 LCM Walk

Description

A frog has just learned some number theory, and can't wait to show his ability to his girlfriend.

Now the frog is sitting on a grid map of infinite rows and columns. Rows are numbered from the bottom, so are the columns. At first the frog is sitting at grid , and begins his journey.

To show his girlfriend his talents in math, he uses a special way of jump. If currently the frog is at the grid , first of all, he will find the minimum that can be divided by both and , and jump exactly steps to the up, or to the right. So the next possible grid will be , or .

After a finite number of steps (perhaps zero), he finally finishes at grid . However, he is too tired and he forgets the position of his starting grid!

It will be too stupid to check each grid one by one, so please tell the frog the number of possible starting grids that can reach !
Input

First line contains an integer , which indicates the number of test cases.

Every test case contains two integers and , which is the destination grid.

.
.
Output

For every test case, you should output " Case #x: y", where indicates the case number and counts from and is the number of possible starting grids.
Sample Input

3
6 10
6 8
2 8
Sample Output

Case #1: 1
Case #2: 2
Case #3: 3

这个题目没什么难度，就是对每个状态求有没有状态能到这个状态，如果有的话就递归。

代码：

#include<iostream>
using namespace std;
 
int gcd(int m, int n)
{
	if (m == 0)return n;
	if (n == 0)return m;
	if (m > n)return gcd(m%n, n);
	return gcd(m, n%m);
}
 
int f(int m, int n)
{
	if (m > n)return f(n, m);
	int g = gcd(m, n);
	if (n % (m + g))return 0;
	int y = n / (m + g)*g;
	if (gcd(m / g, y / g) != 1)return 0;
	return f(m, y) + 1;
}
 
int main()
{	
	ios_base::sync_with_stdio(false);
	int t, m, n;
	cin >> t;
	for (int i = 1; i <= t; i++)
	{
		cin >> m >> n;
		cout << "Case #" << i << ": " << f(m, n) + 1 << endl;
	}
	return 0;
}

CSU 1124 最终时刻

题目：

Description

外太空又发生战争了.机器人王国决定用N架炮台消灭敌人的供需库,但是无奈每架炮台的威力有限,现在国王得到一个消息:如果在某一时刻N架炮台同时打到敌人的供需库,那么这个供需库就会爆炸.当然炮台的威力不累计.也就是说如果某一时刻有N-1架炮台的大炮同时打到敌人的供需库,下一时刻只有第N架炮台的大炮打到敌人供需库的话,供需库是不会爆炸的.现在国王想知最早能在什么时候炸掉敌人的供库.每台大炮的发射间隔是一定的.所有炮从0时刻同时开始发射.

Input

每组数据两行,第一行输入N,表示炮台的数目,接下来的一行有N个数a_1,a_2...a_n,表示每个炮台的发射间隔,N<=1000.a_i<=2^32

Output

每组数据输出一行,表示敌人的供需库最早被炸毁的时间.数据保证最后结果<=2^63-1

Sample Input

Sample Output

6
6

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
 
long long gcd(long long a, long long b)
{
	if (b==0)return a;
	return gcd(b, a%b);
}
 
int main()
{
	long long n, b, ans;
	while (scanf("%lld", &n) != EOF)
	{
		ans = 1;
		while (n--)
		{
			scanf("%lld", &b);
			ans *= b / gcd(ans, b);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

POJ 3101 Astronomy

题目：

Description

There are n planets in the planetary system of star X. They orbit star X in circular orbits located in the same plane. Their tangent velocities are constant. Directions of orbiting of all planets are the same.

Sometimes the event happens in this planetary system which is called planet parade. It is the moment when all planets and star X are located on the same straight line.

Your task is to find the length of the time interval between two consecutive planet parades.

Input

The first line of the input file contains n — the number of planets (2 ≤ n ≤ 1 000).

Second line contains n integer numbers ti — the orbiting periods of planets (1 ≤ ti ≤ 10 000). Not all of ti are the same.

Output

Output the answer as a common irreducible fraction, separate numerator and denominator by a space.

Sample Input

3
6 2 3
Sample Output

3 1

有n个行星,它们的轨道是同一平面上的同向同心圆,且它们始终做匀速圆周运动,周期t1，t2......tn已知

例如，3个行星的周期分别为6,2,3，刚开始的时候都在过恒星的直线上，问下一次都在过恒星的直线上需要的时间T。

这是一个周期的问题，任何2个行星i和j之间都有这样的一个周期T(i,j)——多久一次连线会经过恒星。

这个时间的计算：

如果2个行星周期一样，那么周期T(i,j)=0

如果2个行星周期不一样，那么T(i,j)是使得，在这么长的时间里，2个行星的转角差为半圈

所以T(i,j)=ti*tj / (|ti-tj|*2)，需要化成最简形式

所有的这样的T(i,j)的最小公倍数numerator/denominator即为答案。

计算方法：numerator是所有分子的最小公倍数，denominator是所有分母的最大公约数

不过这个问题，还有一个地方需要注意，“2个行星的连线经过恒星”这个性质是具有传递性的。

所以，并不需要所有的T(i,j)，只需要所有的T(i,i+1)即可。

例如，对于t1=6,t2=2,t3=3，

T(1,2)=6*2 / (4*2)=3/2 , T(2,3)=2*3 / (1*2)=3/1

numerator是分子3和3的最小公倍数3，分母denominator是分母2和1的最大公约数1，所以答案是3 1

c++代码：

#include<iostream>
using namespace std;

int numerator, denominator;

int gcd(int a, int b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}

void f(int num, int den)
{
	if (num % 2 == 0 && den % 2 == 0)
	{
		f(num / 2, den / 2);
		return;
	}
	denominator = gcd(denominator, den);
	numerator *= num / gcd(num, numerator);
}

void g(int a, int b)
{
	if (a == b)return;
	int c = (a > b) ? a - b : b - a;
	f(b / gcd(a, b)*a, c / gcd(a, b) * 2);
}

int main()
{
	numerator = 1, denominator = 0;
	int n, a, b;
	cin >> n >> b;
	while (--n)
	{
		a = b;
		cin >> b;
		g(a, b);
	}
	cout << numerator << " " << denominator << endl;
	return 0;
}

可惜结果是Wrong Answer

原因也很明显，因为numerator会超过int的范围。除此之外程序没有任何问题。

初始化为1/0，然后不断取公倍数即可。

g函数即为计算T(i,i+1)的函数，但是得到的2个数即传到f的2个参数并不一定是互质的，也有可能2个数的最大公约数是2，没有其他情况了。

所以在函数f里面一开始就把可能存在的公约数2去掉了。

函数f即为更新numerator/denominator的函数，只需要n-1次根据f求出公倍数即可得到最后的结果。

对于numerator会超过int的范围这个问题，实际上不止会超过int，numerator有可能非常非常大，只能用大整数。

下面的代码是用java的大整数类：

import java.util.*;
import java.math.BigInteger;
public class Main {

public static BigInteger numerator;
public static int denominator;

public static int gcd(int a, int b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}

public static BigInteger gcd(BigInteger a, BigInteger b)
{
	if (b.equals(BigInteger.valueOf(0)))return a;
	return gcd(b, a.mod(b));
}

public static void f(int num, int den)
{
	if (num % 2 == 0 && den%2==0)
	{
		f(num / 2, den / 2);
		return;
	}
	BigInteger num_=BigInteger.valueOf(num);
	numerator=numerator.multiply(num_.divide(gcd(num_, numerator)));
	denominator = gcd(denominator, den);
}

public static void g(int a, int b)
{
	if (a == b)return;
	int c = (a > b) ? a - b : b - a;
	f(b / gcd(a, b)*a, c / gcd(a, b) * 2);
}
	
public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    numerator = BigInteger.valueOf(1);
    denominator = 0;
	int n, a, b;
	n=Integer.parseInt(cin.next());
	b=Integer.parseInt(cin.next());
	while (--n>0)
	{
		a = b;
		b=Integer.parseInt(cin.next());
		g(a, b);
	}
	System.out.println(numerator.toString()+" "+denominator);     
}

}

这个代码AC了，用了3秒多，差点超时。

方法还是一样，只不过给gcd做了重载，denominator是不会超过10000的，所以用int就可以了

力扣 2470. 最小公倍数为 K 的子数组数目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中满足元素最小公倍数为 k 的子数组数目。

子数组是数组中一个连续非空的元素序列。

数组的最小公倍数是可被所有数组元素整除的最小正整数。

示例 1 ：

输入：nums = [3,6,2,7,1], k = 6
输出：4
解释：以 6 为最小公倍数的子数组是：
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]
示例 2 ：

输入：nums = [3], k = 2
输出：0
解释：不存在以 2 为最小公倍数的子数组。

提示：

1 <= nums.length <= 1000
1 <= nums[i], k <= 1000

class Solution {
public:
    int subarrayLCM(vector<int>& nums, int k) {
        int s=0;
        for(int i=0;i<nums.size();i++){
            int x=nums[i];
            s+=(x==k);
            for(int j=i+1;j<nums.size();j++){
                x=lcm(x,nums[j]);
                if(x>k)break;
                s+=(x==k);
            }
        }
        return s;
    }
};

力扣 878. 第 N 个神奇数字

一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案对 109 + 7 取模后的值。

示例 1：

输入：n = 1, a = 2, b = 3
输出：2

示例 2：

输入：n = 4, a = 2, b = 3
输出：6

提示：

1 <= n <= 109
2 <= a, b <= 4 * 104

class Solution {
public:
	int nthMagicalNumber(int n, int a, int b) {
		gcd = Gcd(a, b), lcm = a * b / gcd;
		int c = num(a * b, a, b);
		int p = 1000000007;
		long long ans = MultiAdd(MultiAdd(n / c, a, p), b, p);
		n %= c;
        cout<<n;
		long long low = 0, high = a * b;
		while (low < high) {
			int mid = (low + high) / 2;
			if (num(mid, a, b) < n)low = mid + 1;
			else high = mid;
		}
		if (num(low, a, b) < n)low++;
		ans += low;
		return ans%p;
	}
private:
	int gcd, lcm;
	int num(int n, int a, int b) {
		return n / a + n / b - n / lcm;
	}
};

力扣 1201. 丑数 III

给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的 正整数 。

示例 1：

输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。

示例 2：

输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。

示例 3：

输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。

示例 4：

输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
输出：1999999984

提示：

1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
本题结果在 [1, 2 * 10^9] 的范围内

class Solution {
public:
	int nthUglyNumber(long long n, int a, int b, int c) {
		ab = Lcm(a, b);
		bc = Lcm(b, c);
		ac = Lcm(a, c);
		abc = Lcm(ab, c);
		long long ans = 0;
		long long low = 0, high = INT_MAX;
		while (low < high) {
			int mid = (low + high) / 2;
			if (num(mid, a, b, c) < n)low = mid + 1;
			else high = mid;
		}
		if (num(low, a, b, c) < n)low++;
		ans += low;
		return ans;
	}
private:
	long long ab, bc, ac, abc;
	long long num(long long n, int a, int b, int c) {
		return n / a + n / b + n / c - n / ab - n / bc - n / ac + (abc ? (n / abc) : 0);
	}
};

力扣 2513. 最小化两个数组中的最大值

给你两个数组 arr1 和 arr2 ，它们一开始都是空的。你需要往它们中添加正整数，使它们满足以下条件：

arr1 包含 uniqueCnt1 个 互不相同 的正整数，每个整数都不能被 divisor1 整除。
arr2 包含 uniqueCnt2 个 互不相同 的正整数，每个整数都不能被 divisor2 整除。
arr1 和 arr2 中的元素 互不相同 。

给你 divisor1 ，divisor2 ，uniqueCnt1 和 uniqueCnt2 ，请你返回两个数组中 最大元素 的 最小值 。

示例 1：

输入：divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3
输出：4
解释：
我们可以把前 4 个自然数划分到 arr1 和 arr2 中。
arr1 = [1] 和 arr2 = [2,3,4] 。
可以看出两个数组都满足条件。
最大值是 4 ，所以返回 4 。

示例 2：

输入：divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
输出：3
解释：
arr1 = [1,2] 和 arr2 = [3] 满足所有条件。
最大值是 3 ，所以返回 3 。

示例 3：

输入：divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2
输出：15
解释：
最终数组为 arr1 = [1,3,5,7,9,11,13,15] 和 arr2 = [2,6] 。
上述方案是满足所有条件的最优解。

提示：

2 <= divisor1, divisor2 <= 105
1 <= uniqueCnt1, uniqueCnt2 < 109
2 <= uniqueCnt1 + uniqueCnt2 <= 109

class Solution:public Bsearch<long long> {
public:
	int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
		d1 = divisor1, d2 = divisor2, n1 = uniqueCnt1, n2 = uniqueCnt2, n = n1 + n2;
		return find(1, INT_MAX);
	}
	bool isOk(long long x) const //若isOk(x)且!isOk(y)则必有y<x
	{
		int x1 = x - x / d1, x2 = x - x / d2, x3 = x-x / Lcm(d1, d2);
		return x1 >= n1 && x2 >= n2 && x3 >= n;
	}
	int d1, d2, n1, n2;
	int n;
};

力扣 2652. 倍数求和

给你一个正整数 n ，请你计算在 [1，n] 范围内能被 3、5、7 整除的所有整数之和。

返回一个整数，用于表示给定范围内所有满足约束条件的数字之和。

示例 1：

输入：n = 7
输出：21
解释：在 [1, 7] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7 。数字之和为 21 。

示例 2：

输入：n = 10
输出：40
解释：在 [1, 10] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9、10 。数字之和为 40 。

示例 3：

输入：n = 9
输出：30
解释：在 [1, 9] 范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9 。数字之和为 30 。

提示：

1 <= n <= 103

class Solution {
public:
	int sumOfMultiples(int n, int a = 3, int b = 5, int c = 7) {
		ab = Lcm(a, b);
		bc = Lcm(b, c);
		ac = Lcm(a, c);
		abc = Lcm(ab, c);
		return num(n, a, b, c);
	}
private:
	long long ab, bc, ac, abc;
	int num(int n, int a, int b, int c) {
		return s(n / a) * a + s(n / b) * b + s(n / c) * c - s(n / ab) * ab - s(n / bc) * bc - s(n / ac) * ac + (abc ? (s(n / abc) * abc) : 0);
	}
	int s(int k)
	{
		return k * (k + 1) / 2;
	}
};

（4）拓展欧几里得算法

CSU 1252 求逆元

题目：

Description

给定正整数x,y，求最小的正整数z使得x*z mod y = 1。

Input

多组数据，每行两个整数x,y 空格隔开。2 <= x, y < 10^6。

Output

输出所求的数，如果小于y的数中不存在这样的数，输出No。

Sample Input

2 3
6 11

Sample Output

2
2

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
 
long long x, y;
 
long long gcd(long long  a, long long b)
{
	if (a == 0 || b == 0)
	{
		x = (b == 0);
		y = (a == 0);
		return a + b;
	}
	long long r;
	if (a < 0)
	{
		r = gcd(-a, b);
		x *= -1;
		return r;
	}
	if (b < 0)
	{
		r = gcd(a, -b);
		y *= -1;
		return r;
	}
	if (a >= b)r = gcd(a%b, b);
	else r = gcd(a, b%a);
	y -= a / b*x;
	x -= b / a*y;
	return r;
}
 
int main()
{
	long long xx, yy;
	while (cin >> xx >> yy)
	{
		if (gcd(xx, yy) == 1)
		{
			if (x < 0)x += yy;
			cout << x << endl;
		}
		else cout << "No\n";
	}
	return 0;
}

HDU 1356 The Balance（拓展欧几里得算法的解空间结构）

题目：

Description

Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine.
For example, to measure 200mg of aspirin using 300mg weights and 700mg weights, she can put one 700mg weight on the side of the medicine and three 300mg weights on the opposite side (Figure 1). Although she could put four 300mg weights on the medicine side and two 700mg weights on the other (Figure 2), she would not choose this solution because it is less convenient to use more weights.
You are asked to help her by calculating how many weights are required.

Input

The input is a sequence of datasets. A dataset is a line containing three positive integers a, b, and d separated by a space. The following relations hold: a != b, a <= 10000, b <= 10000, and d <= 50000. You may assume that it is possible to measure dmg using a combination of amg and bmg weights. In other words, you need not consider "no solution" cases.
The end of the input is indicated by a line containing three zeros separated by a space. It is not a dataset.

Output

The output should be composed of lines, each corresponding to an input dataset (a, b, d). An output line should contain two nonnegative integers x and y separated by a space. They should satisfy the following three conditions.

ﾠﾠ1. You can measure dmg using x many amg weights and y many bmg weights.
ﾠﾠ2. The total number of weights (x + y) is the smallest among those pairs of nonnegative
ﾠﾠintegers satisfying the previous condition.
ﾠﾠ3. The total mass of weights (ax + by) is the smallest among those pairs of nonnegative
ﾠﾠintegers satisfying the previous two conditions.

No extra characters (e.g. extra spaces) should appear in the output.

Sample Input

700 300 200
500 200 300
500 200 500
275 110 330
275 110 385
648 375 4002
3 1 10000
0 0 0

Sample Output

这个题目相对比较难理解，我不解释题意，但是我用精确的语言重新表述以供参考。

输入a,b,d，求所有满足±a*x ±b*y =d的非负整数二元组（x,y）中，x+y最小的那一组，输出x和y。

如果这样的x和y不止一组，输出a*x+b*y最小的一组。

（题目所给数据保证上述二元不定方程一定有解）

这个题目，明显还是要用拓展欧几里得算法，不过还需要一个策略在无穷个解中找出最小解。

这里，需要了解拓展欧几里得算法的解空间结构。

可能你已经知道，如果方程有解，一定有无穷多个解，但是这无穷多个解在二维平面内是怎么分布的呢？

这是我随手画的示意图，能看懂就行。

像这种在y轴上面的截距的绝对值大于x轴上面的截距的绝对值的直线，

最小解要么是x轴上面最低的点A，要么是x轴下面最高的点B，需要比较才知道。

有了这个观念，这个题目就可以解决了。

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
 
long long x, y;
 
long long gcd(long long  a, long long b)
{
	if (a == 0 || b == 0)
	{
		x = (b == 0);
		y = (a == 0);
		return a + b;
	}
	long long r;
	if (a < 0)
	{
		r = gcd(-a, b);
		x *= -1;
		return r;
	}
	if (b < 0)
	{
		r = gcd(a, -b);
		y *= -1;
		return r;
	}
	if (a >= b)r = gcd(a%b, b);
	else r = gcd(a, b%a);
	y -= a / b*x;
	x -= b / a*y;
	return r;
}
 
long long getabs(long long x, long long y)
{
	long long x1 = x, y1 = y;
	if (x1 < 0)x1 = -x1;
	if (y1 < 0)y1 = -y1;
	return x1 + y1;
}
 
void f(long long a, long long b, long long d)
{
	if (a > b)
	{
		f(b, a, d);
		long long t = x;
		x = y;
		y = t;
		return;
	}
	long long g=gcd(a, b);
	x *= d / g;
	y *= d / g;
	while (x < 0)
	{
		x += b / g;
		y -= a / g;
	}
	while (x - b / g >= 0)
	{
		x -= b / g;
		y += a / g;
	}
	if (getabs(x, y) > getabs(x - b / g, y + a / g))
	{
		x -= b / g;
		y += a / g;
	}
}
 
int main()
{
	long long a, b, d;
	while (cin >> a >> b >> d)
	{
		if (a == 0)break;	
		f(a, b, d);
		long long x1 = x, y1 = y;
		if (x1 < 0)x1 = -x1;
		if (y1 < 0)y1 = -y1;
		f(a, b, -d);
		if (x < 0)x = -x;
		if (y < 0)y = -y;
		if (x1 + y1 < x + y)cout << x1 << " " << y1;
		else if (x1 + y1 > x + y)cout << x << " " << y;
		else
		{
			if (a*x1 + b*y1 < a*x + b*y)cout << x1 << " " << y1;
			else cout << x << " " << y;
		}
		cout << endl;
	}
	return 0;
}

SCU 1269、UVA 10090 Marbles

题目：

Description

I have some (say, n) marbles (small glass balls) and I am going to buy some boxes to store them. The boxes are of two types:

Type 1: each box costs c1 Taka and can hold exactly n1 marbles

Type 2: each box costs c2 Taka and can hold exactly n2 marbles

I want each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them. Since I find it difficult for me to figure out how to distribute my marbles among the boxes, I seek your help. I want your program to be efficient also.

Input

The input file may contain multiple test cases. Each test case begins with a line containing the integer n (1 <= n <= 2,000,000,000). The second line contains c1 and n1, and the third line contains c2and n2. Here, c1, c2, n1 and n2 are all positive integers having values smaller than 2,000,000,000.

A test case containing a zero for n in the first line terminates the input.

Output

For each test case in the input print a line containing the minimum cost solution (two nonnegative integers m1 and m2, where mi = number of Type i boxes required) if one exists, print "failed" otherwise.

If a solution exists, you may assume that it is unique.

Sample Input

43
1 3
2 4
40
5 9
5 12
0

Sample Output

13 1
failed

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
 
long long x, y;
 
long long gcd(long long  a, long long b)
{
	if (a == 0 || b == 0)
	{
		x = (b == 0);
		y = (a == 0);
		return a + b;
	}
	long long r;
	if (a < 0)
	{
		r = gcd(-a, b);
		x *= -1;
		return r;
	}
	if (b < 0)
	{
		r = gcd(a, -b);
		y *= -1;
		return r;
	}
	if (a >= b)r = gcd(a%b, b);
	else r = gcd(a, b%a);
	y -= a / b*x;
	x -= b / a*y;
	return r;
}
 
void f(long long n, long long c1, long long n1, long long c2, long long n2)
{
	if (c1*n2 < c2*n1)
	{
		f(n, c2, n2, c1, n1);
		long long t = x;
		x = y;
		y = t;
		return;
	}
	if (n1 == n2)
	{
		x = -1;
		if (n%n2 == 0)
		{
			x = 0;
			y = n / n2;
		}
		return;
	}
	long long g = gcd(n1, n2);
	if (n % g)
	{
		x = -1;
		return;
	}
	x *= n / g;
	y *= n / g;
	long long s = x / (n2 / g);
	x -= n2 / g*s;
	y += n1 / g*s;
	if (x < 0)
	{
		x += n2 / g;
		y -= n1 / g;
	}
}
 
int main()
{
	long long n, c1, n1, c2, n2;
	while (cin >> n)
	{
		if (n == 0)break;
		cin >> c1 >> n1 >> c2 >> n2;
		f(n, c1, n1, c2, n2);
		if (x < 0 || y < 0)cout << "failed" << endl;
		else cout << x << " " << y << endl;
	}
	return 0;
}

POJ 2115 C Looooops

题目：

Description

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.

Input

The input consists of several instances. Each instance is described by a single line with four integers A, B, C, k separated by a single space. The integer k (1 <= k <= 32) is the number of bits of the control variable of the loop and A, B, C (0 <= A, B, C < 2 k) are the parameters of the loop.

The input is finished by a line containing four zeros.

Output

The output consists of several lines corresponding to the instances on the input. The i-th line contains either the number of executions of the statement in the i-th instance (a single integer number) or the word FOREVER if the loop does not terminate.

Sample Input

Sample Output

0
2
32766
FOREVER

题意倒是很简单，就是求满足c*x-2^k*y=b-a的所有（x,y）中，x的最小非负值。

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
 
long long x, y;
 
long long gcd(long long  a, long long b)
{
	if (a == 0 || b == 0)
	{
		x = (b == 0);
		y = (a == 0);
		return a + b;
	}
	long long r;
	if (a < 0)
	{
		r = gcd(-a, b);
		x *= -1;
		return r;
	}
	if (b < 0)
	{
		r = gcd(a, -b);
		y *= -1;
		return r;
	}
	if (a >= b)r = gcd(a%b, b);
	else r = gcd(a, b%a);
	y -= a / b*x;
	x -= b / a*y;
	return r;
}
 
int main()
{
	long long a, b, c, k, con = 1;
	while (cin >> a >> b >> c >> k)
	{
		if (k == 0)break;		
		b -= a;
		k = (con << k);
		if (b == 0)cout << 0;
		else
		{
			long long g = gcd(c, -k);
			if (b%g)cout << "FOREVER";
			else cout << (x*b / g%k + k) % (k / g);
		}
		cout << endl;
	}
	return 0;
}

POJ 1061 青蛙的约会

题目：

Description

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

Input

输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。

Output

输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"

Sample Input

1 2 3 4 5

Sample Output

题意很简单，就是要解方程x+m*t=y+n*t+k*L

其中k可以是任意整数，要求最小非负t

首先要明确，只要求出任何一个满足此方程的t，就可以表示出所有的t，也就得到了最小非负t。

现在只需要做一件事，求任意整数t和k，使得x-y=(n-m)*t+k*L

这个用拓展欧几里得算法就可以了。

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
 
long long x, y;
 
long long gcd(long long  a, long long b)
{
	if (a == 0 || b == 0)
	{
		x = (b == 0);
		y = (a == 0);
		return a + b;
	}
	long long r;
	if (a < 0)
	{
		r = gcd(-a, b);
		x *= -1;
		return r;
	}
	if (b < 0)
	{
		r = gcd(a, -b);
		y *= -1;
		return r;
	}
	if (a >= b)r = gcd(a%b, b);
	else r = gcd(a, b%a);
	y -= a / b*x;
	x -= b / a*y;
	return r;
}
 
int main()
{
	long long xx, yy, m, n, l;
	cin >> xx >> yy >> m >> n >> l;
	xx -= yy;
	n -= m;
	long long g = gcd(n, l);
	if (xx % g == 0)cout << (x*xx / g%l + l) % (l / g) << endl;
	else cout << "Impossible" << endl;
	return 0;
}