首页 > > 程序设计 > C/C++ >

NOIP 2017 Day1 T1 小凯的疑惑

2018-06-17 21:27:54来源：未知阅读 ()

Luogu题面

小学奥数呵呵

在考场上40分钟没证出来（数学太差），运气好看到了规律...

来一波证明：

定义 f(a,b) 表示在 gcd(a,b)==1 情况下的答案。

贝祖定理易证：对于 gcd(c,b)==1，c > a , 有 f(c,b) = f(a,b) + (c-a)*(b-1)

因为我们已知：f(a,b) == f(b,a) ，且 gcd(a,b) == 1

那么我们不妨令 b 为奇数（两数至少一数为奇数）

那么，f(a,b) == f(2,b) + (a-2)*(b-1)

接下来，同理我们解 f(2,b) = f(b,2) = f(3,2) + (b-3)*(2-1) == f(3,2) + (b-3)

由于我们已知：f(2,3) == 1

所以，f(a,b) = f(2,b) + (a-2)*(b-1) = f(3,2) + (b-3) + (a-2)*(b-1) = 1 + b-3 + (ab-2b-a+2) == ab-b-a

证毕。

代码...没多大意义啊...

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,b;  // 不开 LL 会炸掉
    scanf("%lld%lld",&a,&b);
    printf("%lld",a*b-a-b);
    return 0;
}

%%% Dalao 的 ex_gcd

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b){
    return b == 0 ? a : gcd(b, a % b);
}
void ex_gcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1, y = 0; return;
    }
    ex_gcd(b, a % b, y, x);
    y -= (a / b) * x;
}
ll a, b;
int main(){
    cin >> a >> b;
    if(a > b) swap(a, b); 
    ll x, y;
    ex_gcd(a, b, x, y);
    if(x > 0){
        swap(a, b);
        swap(x, y);
    }
    ll tmp = (-x) / b;
    x = x + tmp * b;
    y = y - tmp * a;
    while(x < 0) x = x + b, y = y - a;
    while(x > 0) x = x - b, y = y + a;
    ll ans;
    ll xx2 = x + b;
    ans = a * (xx2 - 1) + b * (y - 1);
    cout << ans - 1 << endl;
    return 0;
}