1.GCD
1.题目描述
给定两个不同的正整数
2.输入格式
输入一行包含两个正整数
3.输出格式
输出一行包含一个正整数
4.样例输入
5 7
5.样例输出
1
6.数据范围
7.原题链接
GCD
2.解题思路
熟悉gcd
的性质的话,根据更相减损术可以知道一个等式:
当然这里前提是
因为 b>=a
,那么我们求的式子就变为了gcd
一定为
时间复杂度:
3.Ac_code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;
LL a, b;
void solve()
{
cin >> a >> b;
if (a > b) swap(a, b);
LL c = b - a;
LL g = a / c;
if (a % c) g++;
cout << (g * c - a) << '\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
版权声明:本文为博主作者:执 梗原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/m0_57487901/article/details/128746000